Leetcode 877. 石子游戏【dp | 数学证明】

骑猪看日落 2022-11-16 13:47 159阅读 0赞

> dp\[l\]\[r\] 代表在区间\[l,r\]中，是否可以获胜  
> 那么 在  
> dp\[l+1\]\[r\] 以及 dp\[l\]\[r-1\]里面只要有一个是输，就可以赢，  
> 因为 \[l+1,r\] 和 \[l,r-1\]这个区间是对手面对的  
> 所以应该是 !(dp\[i+1\]\[i+l\]&&dp\[i\]\[i+l-1\]);  
> 只要有一种可以赢的机会就是赢了

> 然后还需要注意一个地方，就是n=2的时候肯定是赢了  
> 那么就可以推n=1 的时候是输的，但是是与现实不符合的,但是这样可以一直推下去  
> 题目中要求是n>=2可能也是说n=1的时候 与现实冲突吧

class Solution { 
    public:
        bool stoneGame(vector<int>& p) { 
            //return true;
            int n = p.size();
            vector< vector<bool> >dp(n,vector<bool>(n));
            
            for(int i=0;i<n;i++){ 
               dp[i][i] = false;
            }
            
            for(int l=1;l<=n-1;l++){ 
                for(int i=0;i<n;i++){ 
                    if(i+l<n){ 
                        dp[i][i+l] = !(dp[i+1][i+l]&&dp[i][i+l-1]);
                    }
                }
            }
            return dp[0][n-1];
        }
    };

![在这里插入图片描述][20210407140253804.png]  
这个玩意居然可以证明一定可以胜利  
[数学][Link 1]真奇妙

[20210407140253804.png]: /images/20221022/109bf23dcd8e4ffab1da25a88c8190ff.png
[Link 1]: https://leetcode-cn.com/problems/stone-game/solution/shi-zi-you-xi-by-leetcode-solution/

发表评论取消回复

表情：

评论列表（有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode刷题java之877. 石子游戏

行结果：通过显示详情执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户内存消耗 :34.9 MB, 在所有 Java 提交中击败了...

女爷i/ 2024年04月17日 17:54/ 0 赞/ 68 阅读

相关 877. 石子游戏（高频题）

877. 石子游戏题目解题思路代码题目亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles\[i\]

清疚/ 2023年10月05日 20:52/ 0 赞/ 27 阅读

相关 Leetcode 877. 石子游戏【dp | 数学证明】

> dp\[l\]\[r\] 代表在区间\[l,r\]中，是否可以获胜 > 那么在 > dp\[l+1\]\[r\] 以及 dp\[l\]\[r-1\]里面只要有一个

骑猪看日落/ 2022年11月16日 13:47/ 0 赞/ 160 阅读

相关石子合并问题（区间dp）

include <iostream> using namespace std; define ios ios_base::sync_with_stdio

分手后的思念是犯贱/ 2022年10月11日 00:59/ 0 赞/ 191 阅读

相关 877. 石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles\[i\] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。亚历

迈不过友情╰/ 2022年10月07日 04:58/ 0 赞/ 186 阅读

相关 282 石子合并（区间dp）

1. 问题描述：设有 N 堆石子排成一排，其编号为 1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两

朱雀/ 2022年09月12日 12:49/ 0 赞/ 215 阅读

相关 leetcode 877. Stone Game | 877. 石子游戏（递归/动态规划/数学解法）

题目 [https://leetcode.com/problems/stone-game/][https_leetcode.com_problems_stone-game

小鱼儿/ 2022年09月03日 07:26/ 0 赞/ 183 阅读

相关 dp 石子合并问题

石子合并问题：有n(N<100)堆石子，价值分别为a0,a1......a(n-1),每次将其中的相邻的两堆合并，合并的代价为两堆石子的价值和,合并后用合并之后的一堆石子代

￡神魔★判官ぃ/ 2022年08月18日 00:58/ 0 赞/ 211 阅读

相关 877. 石子游戏 and 174. 地下城游戏

> 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 `piles[i]` 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

电玩女神/ 2021年11月11日 06:44/ 0 赞/ 294 阅读

相关取石子游戏

[也许更好的阅读体验][Link 1] \\(\\mathcal\{Description\}\\) ![qsz10914f.png][][![qsz2b35c5.png]

港控/mmm°/ 2021年11月09日 20:04/ 0 赞/ 282 阅读