C++_DP_Recursive_with brief explanation


  • 1

    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];
    }
    };

Log in to reply
 

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