C++ DP with detailed explanation


  • 0

    Suppose we have coins = { 1 , 2 , 5 , 10...M}, index = 0 , 1 , 2 , 3...j.

    Consider the last coin[j] = M, we either use it at least once or don't use it at all,

    if we use it at least once, the amount of money decrease by M, amount = amount - M

    if we don't use it at all, the amount of money stay the same, but the coin set we use becomes coins = 1 , 2 , 5 , 10...M-1; index = 0 , 1 , 2 , 3...j-1.

    And the min exchange solution must be in either with M or without M.

    Therefore, the DP representation would be

    dp[i][j]: Use coins indices from 0 to j to exchange the amount of money i

    dp[i][j] = min{ dp[i][j-1], dp[i-coins[j]][j]+1 }

        int coinChange(vector<int>& coins, int amount) {
            //dp[i][j] = min{ dp[i][j-1], dp[i-coins[j]][j]+1 }
            vector<vector<int>>dp(amount+1,coins);
            for(int i = 0; i < coins.size(); i++) dp[0][i] = 0;
            for(int i = 0; i < amount+1; i++) dp[i][0] = i % coins[0] == 0 ? i / coins[0] : INT_MAX-1;
            for(int i = 1; i < amount+1; i++)
                for(int j = 1; j < coins.size(); j++)
                    if(i >= coins[j]) dp[i][j] = min(dp[i][j-1], dp[i-coins[j]][j]+1);
                    else dp[i][j] = dp[i][j-1];
            return dp[amount][coins.size()-1] == INT_MAX-1 ? -1 : dp[amount][coins.size()-1];
        }
    

Log in to reply
 

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