Coin Change

https://leetcode.com/problems/coin-change/description/

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Thoughts

从一个集合中选择一些凑够一定数目，即想到背包。由于一个硬币能选择无数次，因此是完全背包问题。让f[v]表示在(i, v)时能凑够的最短长度，因此当v = 0时长度为0，初始化v=1,...,amount时没有放任何硬币，自然都没凑满，值为正无穷。为什么选正无穷而不是负无穷呢？因为我们的状态转移方程是求min.

Code

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> f(amount + 1, INT_MAX);
        f[0] = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = coins[i]; j <= amount; ++j) {
                if (f[j - coins[i]] != INT_MAX) f[j] = min(f[j], f[j - coins[i]] + 1);
            }
        }

        return f[amount] == INT_MAX ? -1 : f[amount];
    }
};

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        f[0] = 0;
        for (int j = 1; j <= amount; j++) {
            f[j] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (f[j - coins[i]] != Integer.MAX_VALUE) {
                    f[j] = Math.min(f[j], f[j - coins[i]] + 1);
                }
            }
        }

        return f[amount] == Integer.MAX_VALUE ? -1 : f[amount];
    }
}

Analysis

Errors:

1. f[j - coins[i]] + 1忘了+1.

2. if (f[j - coins[i]] != Integer.MAX_VALUE)没写

时间复杂度为O(N*amount).