# C++_DP_Recursive_with brief explanation

• We use dp[i][j] to indicate the cost if we find our target in range [i,j]. So for each integer k in this range, we have 3 different situation:

1. k == target, this cost = 0;
2. k > target, we need to search in [i,k-1]; and cost is k + dp[i][k-1]
3. k < target, we need to search in [k+1,j]; and cost is k + dp[i][k-1];

From all of these 3 cases, because we want to cover our cost, so we should consider k != target, and choose the k + max(dp[i][k-1],dp[i][k-1] ). Now what is our k value? Because we have the right to choose k, we definitely want to find a k which could minimize our largest cost, so we will choose the k which could min( k + max(dp[i][k-1],dp[i][k-1] ) ). The code is following:

``````class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> dp(n+1,vector<int>(n+1,0));
return DP(1,n,dp);
}
int DP(int start, int end, vector<vector<int>>& dp){
if(start >= end) return 0;
if(dp[start][end] != 0) return dp[start][end];// this range has been searched!
int res = INT_MAX;
for(int k = start; k < end; ++k){
int max_sub = k + max(DP(start,k - 1,dp), DP(k + 1, end, dp));
res = min(res, max_sub);
}
dp[start][end] = res;
return dp[start][end];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.