 / 递推(DP+原地滚动))
【LetMeFly】1406.石子游戏 III递归(DFS记忆化) / 递推(DP原地滚动)力扣题目链接https://leetcode.cn/problems/stone-game-iii/Alice 和 Bob 继续他们的石子游戏。几堆石子排成一行每堆石子都对应一个得分由数组stoneValue给出。Alice 和 Bob 轮流取石子Alice总是先开始。在每个玩家的回合中该玩家可以拿走剩下石子中的的前1、2 或 3 堆石子。比赛一直持续到所有石头都被拿走。每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是0。比赛的目标是决出最高分得分最高的选手将会赢得比赛比赛也可能会出现平局。假设 Alice 和 Bob 都采取最优策略。如果 Alice 赢了就返回AliceBob 赢了就返回Bob分数相同返回Tie。示例 1输入values [1,2,3,7]输出Bob解释Alice 总是会输她的最佳选择是拿走前三堆得分变成 6 。但是 Bob 的得分为 7Bob 获胜。示例 2输入values [1,2,3,-9]输出Alice解释Alice 要想获胜就必须在第一个回合拿走前三堆石子给 Bob 留下负分。 如果 Alice 只拿走第一堆那么她的得分为 1接下来 Bob 拿走第二、三堆得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆输掉比赛。 如果 Alice 拿走前两堆那么她的得分为 3接下来 Bob 拿走第三堆得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆同样会输掉比赛。 注意他们都应该采取最优策略所以在这里 Alice 将选择能够使她获胜的方案。示例 3输入values [1,2,3,6]输出Tie解释Alice 无法赢得比赛。如果她决定选择前三堆她可以以平局结束比赛否则她就会输。提示1 stoneValue.length 5 * 104-1000 stoneValue[i] 1000解题方法一深度优先搜索写一个函数计算 从s t o n e V a l u e [ i d x ] stoneValue[idx]stoneValue[idx]开始拿到最后的子游戏 中先手最多比后手领先多少分。怎么计算如果已经拿空则返回0 00否则返回三种选法中结果最好的那个(如有)时间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))空间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))AC代码C/* * LastEditTime: 2026-08-03 18:36:37 */classSolution{private:intn;vectorintmem;intplay(vectorintv,intidx0){if(mem[idx]!INT_MIN){returnmem[idx];}if(idxn){returnmem[idx]0;}intansINT_MIN;for(inti0,cnt0;i3;i){if(idxin){break;}cntv[idxi];ansmax(ans,cnt-play(v,idxi1));}returnmem[idx]ans;}public:stringstoneGameIII(vectorintstoneValue){nstoneValue.size();mem.resize(n1,INT_MIN);intscoreplay(stoneValue);returnscore0?Alice:score?Bob:Tie;}};解题方法二.1动态规划令d p [ i ] dp[i]dp[i]代表当前先手从下标i ii选到最后的最大得分s u f f i x [ i ] suffix[i]suffix[i]代表从下标i ii选到最后的总分。则当前先手在下标i ii选择j jj个的话相当于其对手从下标i j ijij开始到最后作为先手当前先手的得分为后面总分减去对手得分即s u f f i x [ i ] − d p [ i j ] suffix[i]-dp[ij]suffix[i]−dp[ij]。时间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))空间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))AC代码C/* * LastEditTime: 2026-08-03 18:55:21 */classSolution{public:stringstoneGameIII(vectorintstoneValue){vectorintdp(stoneValue.size()3);intsuffix0;for(intistoneValue.size()-1;i0;i--){dp[i]INT_MIN;suffixstoneValue[i];for(intj1;j3;j){dp[i]max(dp[i],suffix-dp[ij]);}}intdiffdp[0]-(suffix-dp[0]);returndiff0?Alice:diff?Bob:Tie;}};解题方法二.2动态规划原地滚动不难发现j jj的取值范围是1 ≤ j ≤ 3 1\leq j\leq 31≤j≤3所以我们使用三个变量来存放后面三个d p dpdp值就好了。时间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))空间复杂度O ( 1 ) O(1)O(1)AC代码C/* * LastEditTime: 2026-08-03 19:01:21 */classSolution{public:stringstoneGameIII(vectorintstoneValue){intdp3[3]{0};intsuffix0;for(intistoneValue.size()-1;i0;i--){intdpINT_MIN;suffixstoneValue[i];for(intj0;j3;j){dpmax(dp,suffix-dp3[j]);}dp3[2]dp3[1],dp3[1]dp3[0],dp3[0]dp;}intdiffdp3[0]-(suffix-dp3[0]);returndiff0?Alice:diff?Bob:Tie;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源
【LetMeFly】1406.石子游戏 III递归(DFS记忆化) / 递推(DP原地滚动)力扣题目链接https://leetcode.cn/problems/stone-game-iii/Alice 和 Bob 继续他们的石子游戏。几堆石子排成一行每堆石子都对应一个得分由数组stoneValue给出。Alice 和 Bob 轮流取石子Alice总是先开始。在每个玩家的回合中该玩家可以拿走剩下石子中的的前1、2 或 3 堆石子。比赛一直持续到所有石头都被拿走。每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是0。比赛的目标是决出最高分得分最高的选手将会赢得比赛比赛也可能会出现平局。假设 Alice 和 Bob 都采取最优策略。如果 Alice 赢了就返回AliceBob 赢了就返回Bob分数相同返回Tie。示例 1输入values [1,2,3,7]输出Bob解释Alice 总是会输她的最佳选择是拿走前三堆得分变成 6 。但是 Bob 的得分为 7Bob 获胜。示例 2输入values [1,2,3,-9]输出Alice解释Alice 要想获胜就必须在第一个回合拿走前三堆石子给 Bob 留下负分。 如果 Alice 只拿走第一堆那么她的得分为 1接下来 Bob 拿走第二、三堆得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆输掉比赛。 如果 Alice 拿走前两堆那么她的得分为 3接下来 Bob 拿走第三堆得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆同样会输掉比赛。 注意他们都应该采取最优策略所以在这里 Alice 将选择能够使她获胜的方案。示例 3输入values [1,2,3,6]输出Tie解释Alice 无法赢得比赛。如果她决定选择前三堆她可以以平局结束比赛否则她就会输。提示1 stoneValue.length 5 * 104-1000 stoneValue[i] 1000解题方法一深度优先搜索写一个函数计算 从s t o n e V a l u e [ i d x ] stoneValue[idx]stoneValue[idx]开始拿到最后的子游戏 中先手最多比后手领先多少分。怎么计算如果已经拿空则返回0 00否则返回三种选法中结果最好的那个(如有)时间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))空间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))AC代码C/* * LastEditTime: 2026-08-03 18:36:37 */classSolution{private:intn;vectorintmem;intplay(vectorintv,intidx0){if(mem[idx]!INT_MIN){returnmem[idx];}if(idxn){returnmem[idx]0;}intansINT_MIN;for(inti0,cnt0;i3;i){if(idxin){break;}cntv[idxi];ansmax(ans,cnt-play(v,idxi1));}returnmem[idx]ans;}public:stringstoneGameIII(vectorintstoneValue){nstoneValue.size();mem.resize(n1,INT_MIN);intscoreplay(stoneValue);returnscore0?Alice:score?Bob:Tie;}};解题方法二.1动态规划令d p [ i ] dp[i]dp[i]代表当前先手从下标i ii选到最后的最大得分s u f f i x [ i ] suffix[i]suffix[i]代表从下标i ii选到最后的总分。则当前先手在下标i ii选择j jj个的话相当于其对手从下标i j ijij开始到最后作为先手当前先手的得分为后面总分减去对手得分即s u f f i x [ i ] − d p [ i j ] suffix[i]-dp[ij]suffix[i]−dp[ij]。时间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))空间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))AC代码C/* * LastEditTime: 2026-08-03 18:55:21 */classSolution{public:stringstoneGameIII(vectorintstoneValue){vectorintdp(stoneValue.size()3);intsuffix0;for(intistoneValue.size()-1;i0;i--){dp[i]INT_MIN;suffixstoneValue[i];for(intj1;j3;j){dp[i]max(dp[i],suffix-dp[ij]);}}intdiffdp[0]-(suffix-dp[0]);returndiff0?Alice:diff?Bob:Tie;}};解题方法二.2动态规划原地滚动不难发现j jj的取值范围是1 ≤ j ≤ 3 1\leq j\leq 31≤j≤3所以我们使用三个变量来存放后面三个d p dpdp值就好了。时间复杂度O ( l e n ( s t o n e V a l u e ) ) O(len(stoneValue))O(len(stoneValue))空间复杂度O ( 1 ) O(1)O(1)AC代码C/* * LastEditTime: 2026-08-03 19:01:21 */classSolution{public:stringstoneGameIII(vectorintstoneValue){intdp3[3]{0};intsuffix0;for(intistoneValue.size()-1;i0;i--){intdpINT_MIN;suffixstoneValue[i];for(intj0;j3;j){dpmax(dp,suffix-dp3[j]);}dp3[2]dp3[1],dp3[1]dp3[0],dp3[0]dp;}intdiffdp3[0]-(suffix-dp3[0]);returndiff0?Alice:diff?Bob:Tie;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源
)
