[Leetcode][第486題][JAVA][預測赢家][動态規劃][遞歸]

【問題描述】[中等]

【解答思路】

1.遞歸

複雜度

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 步：狀态轉移方程

第 3 步：考慮初始化

第 4 步：考慮輸出

dp[0][length]

第 5 步：考慮是否可以狀态壓縮

是

時間複雜度：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;
    }
}




           

時間複雜度：O(N2) 空間複雜度：O(N)

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.算法思想

【資料結構與算法】【算法思想】動态規劃

轉載連結：https://leetcode-cn.com/problems/predict-the-winner/solution/yu-ce-ying-jia-by-leetcode-solution/