[Leetcode][第486题][JAVA][预测赢家][动态规划][递归]

淡淡的烟草味﹌ 2022-12-03 02:21 172阅读 0赞

#### 【问题描述】\[中等\] ####

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

#### 【解答思路】 ####

###### 1.递归 ######

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

**复杂度**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

class Solution { 
        public boolean PredictTheWinner(int[] nums) { 
            return total(nums,0,nums.length-1,1) >=0;
        }
        //turn 标记轮到谁了 正数表示先手 负数表示后手 
        public  int total( int[]nums ,int start,int end,int turn){ 
            if(start == end){ 
                return   nums[start]*turn;
            }
    
            int scoreStart = nums[start]*turn +total(nums,start+1,end,-turn);
            int scoreEnd = nums[end] *turn +total(nums,start ,end-1,-turn);
            //先选绝对值最大的那个分数，再把它转换成先后手选手对应的正分或负分
            // return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
            if(turn == 1){ 
                return Math.max(scoreStart,scoreEnd);
            }else{ 
                return Math.min(scoreStart,scoreEnd);
            }
    
    
        }
    }

###### 2. 动态规划 ######

方法一使用递归，存在大量重复计算，因此时间复杂度很高。由于存在重复子问题，因此可以使用动态规划降低时间复杂度。  
第 1 步：设计状态  
定义二维数组dp，其行数和列数都等于数组的长度，dp\[i\]\[j\] 表示当数组剩下的部分为下标 i 到下标 j 时，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。

第 2 步：状态转移方程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]

第 3 步：考虑初始化  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]

第 4 步：考虑输出  
**dp\[0\]\[length\]**  
第 5 步：考虑是否可以状态压缩  
是![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]

**时间复杂度：O(N2) 空间复杂度：O(N2)**

class Solution { 
        public boolean PredictTheWinner(int[] nums) { 
            int length = nums.length;
            int[][] dp = new int[length][length];
            for (int i = 0; i < length; i++) { 
                dp[i][i] = nums[i];
            }
            for (int i = length - 2; i >= 0; i--) { 
                for (int j = i + 1; j < length; j++) { 
                    dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
                }
            }
            return dp[0][length - 1] >= 0;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 8]

**时间复杂度：O(N2) 空间复杂度：O(N)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 9]

class Solution { 
        public boolean PredictTheWinner(int[] nums) { 
            int length = nums.length;
            int[] dp = new int[length];
            for (int i = 0; i < length; i++) { 
                dp[i] = nums[i];
            }
            for (int i = length - 2; i >= 0; i--) { 
                for (int j = i + 1; j < length; j++) { 
                    dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
                }
            }
            return dp[length - 1] >= 0;
        }
    }

#### 【总结】 ####

###### 1. 动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.递归 自上而下 动态规划 自底向上 ######

###### 3.算法思想 ######

[【数据结构与算法】【算法思想】动态规划][Link 1]

转载链接：https://leetcode-cn.com/problems/predict-the-winner/solution/yu-ce-ying-jia-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/a016c4f7f22d4ee59463f51377ba6d29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/988c5ba3497b4625a41a6a1f4bf19ad1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/de2190bfce644dadabc4c4bc4513f040.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/9118f2b48a044ebc8ba23a8f27640151.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/f05cd1a409e04ebabe7e5d15a0e975ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/5822d28e948a47608d2a64df3fd33979.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/984df584ceac412687e58d00de4b18a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/d0a34416c90d4668a069ca070e706815.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/3b3ea5cb63f44d779f563c6aeea640de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/57cd1218d9ba4526b0eef30df0926d7a.png
[Link 1]: https://blog.csdn.net/dadongwudi/article/details/108263805