88ms DP C++ Solution with full comment and detailed explanation


  • 0
    A

    This is a classical Dynamic Programming problem, and to solve it we must find the recurrence function between states.

    So we can define a function/state f[i][v], which is the minimum number of coins used to sum up to v, and i is the number of different denominations used for this sum (use the first i denominations in coins).

    f[i][v] = min {case1, case2}

    Case1 is f[i-1][v], where coins[i] isn't used;

    Case2 is f[i][v-coins[i-1]]+1, where coins[i] is used (and can be used multiple times)

    So the weight-lifting work is now finished, and all we have to do is to iterate i from 1 to coins.size() (set count[0] to 0, obviously), while for each i we update coins[v] from v=cost[i-1] to v=amount (no need to start from v=0, because count[v-coins[i-1]] is meaningful only when v-coins[i-1]>0

    After finishing all this, return count[amount] as the final result (if count[amouint] is still INT_MAX, which means the search fails, then return -1)

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            int count[amount+1]; // count[v] is minimum coin count that can add up to v
            count[0] = 0; // Target value 0 can always be achieved by using no coin at all
            for (int i=1;i<=amount;i++)
                count[i] = INT_MAX;
            for (int j=1;j<=coins.size();j++) { // Use the first j kinds of coins (each kind can be used more than once)
                for (int v=coins[j-1];v<=amount;v++) { // If current v is less than coins[i], then we have only one cadidate count[v] and don't need to compare
                    count[v] = min(count[v], (count[v-coins[j-1]])==INT_MAX?INT_MAX:(count[v-coins[j-1]]+1)); // If count[v-coins[j-1]] is already INT_MAX, then +1 will make it negative, and save this negative value as the new count[v]. Thus add an additional contion to prevent that.
                }
            }
            if (count[amount] == INT_MAX)
                return -1;
            return count[amount];
        }
    };

Log in to reply
 

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