375. 猜数字大小 II

 1 class Solution 
 2 {
 3     vector<vector<int>> memo;
 4 public:
 5     int getMoneyAmount(int n) 
 6     {
 7         memo = vector<vector<int>>(n + 1,vector<int>(n + 1,-1));
 8         return calculate(1, n);
 9     }
10 
11     int calculate(int low, int high) 
12     {
13         if(memo[low][high] != -1) return memo[low][high];
14         if (low == high) return 0;
15         int res = INT_MAX, m = 0, left = 0, right = 0;
16         //利用minmax + 备忘录
17         for (int i = low; i <= high; i++) 
18         {
19             if(i - 1 >= low) left = calculate(low,i - 1);
20             if(i + 1 <= high) right = calculate(i + 1,high);
21             m = i + max(left,right);
22             res = min(res,m);
23         }
24         memo[low][high] = res;
25         return res;
26     }
27 };