My C++ dynamic programming solution with explaination


  • 0

    (1) you should sort coins.(record the smallest)

    (2) traverse the result vector from the smallest coin

    (3) result[i] = result[j] + 1(j < i and exist k that j + coins[k] equals i). otherwise, result[i] = -1

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            if(!amount)
            {
                return 0;
            }
            if(!coins.size())
            {
                return -1;
            }
            vector<int> result(amount + 1, -1);
            sort(coins.begin(), coins.end());
            int start = coins[0];
            for(int i = 0; i < coins.size(); i++)
            {
                if(coins[i] <= amount)
                {
                    result[coins[i]] = 1;
                }
            }
            for(int i = start + 1; i <= amount; i++)
            {
                int min = INT_MAX;
                if(result[i] == 1)
                {
                    continue;
                }
                for(int k = 0; k < coins.size() && i - coins[k] >= start; k++)
                {
                    if(result[i - coins[k]] != -1)
                    {
                        min = min > result[i - coins[k]] + 1 ? result[i - coins[k]] + 1 : min;
                    }
                }
                result[i] = min == INT_MAX ? -1 : min;
            }
            return result[amount];
        }
    };

Log in to reply
 

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