leetcode

0 class Solution {

1 static int dp[201][201];

2

3 static int rec(int a, int b) {

4 if (a >= b) return 0;

5 if (dp[a][b] != 0) return dp[a][b];

6

7 int res = INT_MAX;

8 for (int i = (a + b) / 2; i <= b; i++) {

9 res = min(i + max(rec(i + 1, b), rec(a, i - 1)), res);

10 }

11

12 return dp[a][b] = res;

13 }

14

15 public:

16 int getMoneyAmount(int n) const {

17 memset(dp, 0x00, sizeof(dp));

18 return rec(1, n);

19 }

20 };

21

22 int Solution::dp[201][201];