[leetcode] 322. Coin Change

https://leetcode.com/problems/coin-change/?tab=Description

Solution:
A good question for dynamic programming. It also belongs to 01 knapsack problem. Let's suppose dp[i] represents the minimum coins needed to make up the amount, then the transition formula will be
              dp[i] = min(dp[i], dp[i-c[j]] + 1),   c[j] <= i;

Some details for implementation:
1): dp[0] can be set as 0; since it means the minimum number of coins needed for 0 is 0, which is legal based on the definition of dp[0];
2): All the rest dp[i] can be set (as amount + 1) since if there's at least one way to make up the amount, then minimum coins needed will be no larger than amount itself, because the worst situation (or the largest) is there are coins with 1 as the denomination and it is the only way to make up the amount.
3): to speed up a little bit, we can sort the coins. For coins bigger than i, we can just ignore them.

Code:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) return 0;
        if(coins.empty()) return -1;
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        sort(coins.begin(), coins.end());
        for(int i=1; i<=amount; ++i){
            for(int j=0; j<coins.size(); ++j){
                if(i>=coins[j]){
                    dp[i] = min(dp[i], dp[i-coins[j]] + 1);
                }
                else break;
            }
        }
        return dp[amount]==amount + 1?-1:dp[amount];
    }
};