486. Predict the Winner

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/predict-the-winner/description/

想法

DP 算出num[x][y]

1
2
3
4
num[0][0] = n[0]
num[0][1] = max(n[0][0], n[1][1])
...
num[x][y] = max(n[x] + sum[x+1][y] - num[x+1][y], n[y] + sum[x][y-1] - num[x][y-1])

先算 num[i][i]
再算 num[i-1][i]
最后 num[0][N]

答案

虽然想的过程有些不顺利，但是一遍AC了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int m[20][20] = {0};
        int sum[20][20] = {0};
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0, k = i; k < nums.size(); j++, k++) {
                if (j == k) {
                    m[j][k] = sum[j][k] = nums[j];
                } else {
                    sum[j][k] = sum[j][k - 1] + nums[k];
                    m[j][k] = max(nums[j] + sum[j+1][k] - m[j + 1][k], nums[k] + sum[j][k - 1] - m[j][k - 1]);
                }
            }
        }
        
        return m[0][nums.size() - 1] >= sum[0][nums.size() - 1] - m[0][nums.size() - 1];
    }
};

回顾

DP的题目，一般是想出来基本就比较容易了

这个题目的DP不是从最小到最大，也不是从最大到最小（不是一行一行的推进或者一列一列的推进），而是从对角线开始，向上推进的，也算是一种比较新的思路吧