leetcode1140 Stone Game II

 1 class Solution
 2 {
 3 public:
 4     int dfs(vector<int>& sum, int cur, int M, vector<vector<int>>& dp)
 5     {
 6         int n = sum.size(); 
 7         if (n - cur <= 2 * M) return sum[n - 1] - sum[cur];
 8         if (dp[cur][M] != -1) return dp[cur][M];
 9         int ans = INT_MIN;
10         for (int i = 1; i <= min(2 * M, n - cur); i++)
11         {
12             int tmp = dfs(sum, cur + i, max(M, i), dp);
13             ans = max(ans, sum[cur + i - 1] - sum[cur] + sum[n - 1] - sum[cur + i - 1] - tmp);
14         }
15         return dp[cur][M] = ans;
16     }
17     int stoneGameII(vector<int>& piles)
18     {
19         int n = piles.size();
20         vector<int> sum(n + 1, 0);
21         vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
22         for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + piles[i - 1];
23         int res = dfs(sum, 0, 1, dp);
24         return res;
25     }
26 }