leetcode

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

0375.cpp (499B)

      1 class Solution {
      2     static int dp[201][201];
      3 
      4     static int rec(int a, int b) {
      5         if (a >= b) return 0;
      6         if (dp[a][b] != 0) return dp[a][b];
      7 
      8         int res = INT_MAX;
      9         for (int i = (a + b) / 2; i <= b; i++) {
     10             res = min(i + max(rec(i + 1, b), rec(a, i - 1)), res);
     11         }
     12 
     13         return dp[a][b] = res;
     14     }
     15 
     16   public:
     17     int getMoneyAmount(int n) const {
     18         memset(dp, 0x00, sizeof(dp));
     19         return rec(1, n);
     20     }
     21 };
     22 
     23 int Solution::dp[201][201];