leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1140.cpp (629B)

      1 class Solution {
      2     int dp[10001][101];
      3 
      4   public:
      5     Solution() { memset(dp, 0, sizeof(dp)); }
      6 
      7     int stoneGameII(const vector<int> &piles) {
      8         int n = piles.size();
      9         vector<int> sum(n + 1, 0);
     10         for (int i = n - 1; i >= 0; i--) {
     11             dp[i][n] = sum[i] = sum[i + 1] + piles[i];
     12         }
     13 
     14         for (int i = n - 1; i >= 0; i--) {
     15             for (int j = n - 1; j >= 1; j--) {
     16                 for (int X = 1; X <= 2 * j && i + X <= n; X++) {
     17                     dp[i][j] = max(dp[i][j], sum[i] - dp[i + X][max(j, X)]);
     18                 }
     19             }
     20         }
     21         return dp[0][1];
     22     }
     23 };