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

小鱼儿 2022-09-03 07:26 166阅读 0赞

## 题目 ##

[https://leetcode.com/problems/stone-game/][https_leetcode.com_problems_stone-game]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

一开始写了个递归，超时了。没想出怎么写 dp，看了答案之后写的。

整体草稿：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

#### 方法1：递归（超时） ####

class Solution { 
        public boolean stoneGame(int[] piles) { 
            int target = 0;
            for (int n : piles) { 
                target += n;
            }
            target /= 2;
            
            return pick(0, piles.length - 1, piles, 0, target, true);
        }
    
        // 所有无后效性的递归都可以改写成dp？本题有后效性吗？
        public boolean pick(int L, int R, int[] piles, int sum, int target, boolean turn) { 
            if (sum > target) return true;
            if (L == R) { 
                return false;
            } else if (turn) { 
                return pick(L + 1, R, piles, sum + piles[L], target, false) || pick(L, R - 1, piles, sum + piles[R], target, false);
            } else { 
                return pick(L + 1, R, piles, sum, target, true) || pick(L, R - 1, piles, sum, target, true);
            }
        }
    }

#### 方法2：动态规划 ####

参考：[官方题解][Link 1]，有动图演示，比较好懂一些  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]

class Solution { 
        public boolean stoneGame(int[] piles) { 
            int n = piles.length;
            int[][] dp = new int[n + 2][n + 2];
            for (int i = 0; i < n; i++) { 
                dp[i + 1][i + 1] = piles[i];
            }
            for (int i = n - 1; i >= 0; i--) {  // dp多一层0可节省边界判断，但要注意错位对应
                for (int j = i + 1; j < n; j++) { 
                    dp[i + 1][j + 1] = Math.max(piles[j] - dp[i + 1][j], piles[i] - dp[i + 2][j + 1]);
                }
            }
            return dp[1][n] > 0;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

#### 方法3：数学方法 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_stone-game]: https://leetcode.com/problems/stone-game/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/9732b8074da547358dc3aadbb29dcb80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/f6330f9e57fb48729b28c1a66613af41.png
[Link 1]: https://leetcode-cn.com/problems/stone-game/solution/shi-zi-you-xi-by-leetcode-solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/c2f4d42977a44af081f6daf63ae9f8d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20220829/5a6076eb6bb24ada8f88f38e33397384.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/9a3996dfd3364c3e8af428268b7e86a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20220829/3311018d6eb94a5d8683c405f8617f54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/da65e6d6c123434c93aaadadadb7908c.png