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.

Note:
You may assume that you have an infinite number of each kind of coin.

最基础的DP,用个minCoin[i]存到第i个钱数时候的最少硬币数量,

转移方程: minCoin[i] = min{ minCoin[i], minCoin[i-coin[j]] + 1 },该题将初始值设为-1,注意到每个i初始化minCoin[i]要判断是否是-1来决定用转移方程比较还是直接初始化。另外要注意的转移方程的满足条件要求i-coin[j] >= 0,另外转移中的min[i – coin[j]] != -1。该算法时间复杂度O(N*M)。

Solution:


class Solution {
public:
        int DP[10000];
        int coinChange(vector<int>& coins, int amount) {
                if(amount == 0) return 0;
                if(coins.size() < 1) return -1;
                memset(DP, -1, 10000 * sizeof(int));
                DP[0] = 0;
                for(int i = 1; i <= amount; ++i)
                {
                        for(int j = 0; j < coins.size(); ++j)
                        {
                                if(i - coins[j] >= 0)
                                {
                                        if(DP[i] != -1 && DP[i - coins[j]] != -1)
                                        DP[i] = min(DP[i], DP[i - coins[j]] + 1);
                                        else if(DP[i] == -1 && DP[i - coins[j]] != -1)
                                        DP[i] = DP[i - coins[j]] + 1;
                                }
                        }
                }
                return DP[amount];
        }
};
144ms

Leave a Reply

Your email address will not be published. Required fields are marked *