LeetCode486. Predict the Winner

题目传送门

题意

两个人交替从一个数组两端获取一个数字，每次每个人只能获取一个，最终获取的数字之和最大的获胜，问第一个人能否获胜？

分析

最优子结构：dp[i][j]维护从i到j获取的所有数字之和的最大值，则dp[i+1][j]表示第二个人能够在i-1到j之间获取的所有数字之和的最大值，dp[i][j-1]表示第二个人能够在i到j-1之间获取的所有数字之和的最大值。

sum[i][j]维护 i 到 j 所有数字之和，因为两个人都想赢，即每个人都取最优解，所以sum[i+1][j] - dp[i+1][j]表示第一个人取第i个元素以后，能够在 i+1 到 j 之间获取子数组之和的最大值，sum[i][j-1] - dp[i][j-1]标识第一个人取第j个元素以后，能够在 i 到 j-1 之间获取子数组之和的最大值。

状态转移方程：
dp[i][j] = max{ nums[i]+sum[i+1][j]-dp[i+1][j], nums[j]+sum[i][j-1]-dp[i][j-1]}
当i == j时，只有一种选择，dp[i][j] = nums[i]
当i == j-1 时，只有两种选择，dp[i][j] = max(nums[i], nums[j])

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        int[] presum = new int[n+1];
        for(int i = 0;i < n;i++) {
            presum[i+1] = presum[i]+nums[i];
        }
        for(int len = 1;len <= n;len++)//长度为n的最优解需要用到长度为n-1的最优解
            for(int l = 0;l + len - 1 < n;l++){
                int r = l + len - 1;
                if(l==r){
                    dp[l][r] = nums[l];
                }
                else if(l == r-1){
                    dp[l][r] = Math.max(nums[l],nums[r]);
                }
                else{
                    dp[l][r] = Math.max(nums[l]+presum[r+1]-presum[l+1]-dp[l+1][r],
                                        nums[r]+presum[r]-presum[l]-dp[l][r-1]);
                }
            }
        return dp[0][n-1]*2>=presum[n];
    }
}

留言

2017-02-23
⬆︎TOP