375. Guess Number Higher or Lower II

Let dp[i][j] be the minimum cost among  [i...j] on worst cases. So, To compute dp[i][j], we need to traverse every number among [i...j] for worst cases cost and select the minimum cost among these worst cases.
To compute worst case for k in [i...j], we have worst = (k + max(dp[i][k-1], dp[k+1][j])).
To get the minimum cost among [i...j], we just pick the choose min(cost, worst) for each worst.

1:  class Solution {  
2:  public:  
3:    int getMoneyAmount(int n) {  
4:      vector<vector<int>> dp(n+1, vector<int>(n+1, 0));  
5:      return helper(dp, 1, n);  
6:    }  
7:    int helper(vector<vector<int>> &dp, int s, int e) {  
8:      if (s >= e) return 0;  
9:      if (dp[s][e] != 0) return dp[s][e];  
10:      int cost = INT_MAX;  
11:      for (int i = s; i <= e; i++) {  
12:        int worst = i + max(helper(dp, s, i-1), helper(dp, i+1, e));  
13:        cost = min(cost, worst);  
14:      }  
15:      dp[s][e] = cost;  
16:      return cost;  
17:    }  
18:  };