Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

https://leetcode.com/problems/predict-the-winner/description/
486. Predict the Winner
給定一個陣列 nums ， nums[i] 表示第 i 個物品的分數，有兩個玩家AB輪流從
nums 的最左或最右元素裡面取一個元素並得到該分數，若A和B的每一步都是最
聰明的選擇，返回A先選的情況是否分數總是比B大（相等的情況仍是A贏）。

Example 1:
Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If
player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return false.

Example 2:
Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5
and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to
return True representing player1 can win.

思路：
1.選和不選的問題基本上都是動態規劃問題，所以先從遞迴方式來考慮解決此問題。

2.當 nums 長度為1的時候，很明顯最佳的選擇就是唯一的元素
  當 nums 長度為2的時候，很明顯最佳選則會是 MAX(nums[0], nums[1])
  當 nums 長度為3的時候，最佳選擇可以分成拿左和拿右

  拿左的最佳選擇：nums[0] - 玩家二在 nums[1~2] 可獲得的最大分數
  拿右的最佳選擇：nums[2] - 玩家二在 nums[0~1] 可獲得的最大分數
  上面兩個選擇取較大的就是長度3的最佳分數

  當 nums 大於 3 的時候繼續推導，不失一般性。

3.有遞迴關係式之後就可以寫成 dfs 形式了，其中陣列 [i,j] 之間可獲得的最大分數
  會重複遞迴好幾次，所以可以用一個 memo 去紀錄（DP）。

4.最後判斷返回值是否大於0就好。

Java Code：
--------------------------------------------------------
class Solution {
    private int[][] memo;
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        memo = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], Integer.MIN_VALUE);
        }
        return dfs(nums, 0, n - 1) >= 0;
    }
    private int dfs(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        if (memo[l][r] != Integer.MIN_VALUE) {
            return memo[l][r];
        }
        int takeLeft = nums[l] - dfs(nums, l + 1, r);
        int takeRight = nums[r] - dfs(nums, l, r - 1);
        return memo[l][r] = Math.max(takeLeft, takeRight);
    }
}
--------------------------------------------------------

懶得迭代= =
--
https://i.imgur.com/uiFto42.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690554425.A.EAD.html
※ 編輯: Rushia (122.100.75.86 臺灣), 07/28/2023 22:28:51
推 Che31128: 大師
推 ILoveErr: 大師