Guess Number Higher or Lower II LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<vector<int>> dp;
4

5
  int solve(int start, int end) {
6
    if (start >= end) return 0;
7

8
    if (dp[start][end] != -1) return dp[start][end];
9

10
    int ans = 0;
11
    int result = INT_MAX;
12
    for (int i = start; i <= end; i++) {
13
      int left = solve(start, i - 1);
14
      int right = solve(i + 1, end);
15
      ans = max(left, right) + i; // this line gurantee to include the money
16
                                  // that is needed to win higher values
17
      result = min(ans, result);
18
    }
19

20
    return dp[start][end] = result;
21
  }
22

23
  int getMoneyAmount(int n) {
24
    int ans = 0;
25
    dp = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
26
    return solve(1, n);
27
  }
28
};