零钱兑换(coin-change) 动态规划问题_coin change

零钱兑换(coin-change)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
1
2
3

示例 2:

输入: coins = [2], amount = 3
输出: -1
1
2

说明:
你可以认为每种硬币的数量是无限的。

思路

假设你是个土豪，你有1，5，10，20，50，100的钞票，你要凑出666买瓶水喝，依据生活经验，我们一般采取这样的策略：能用100就用100的，否则就用50的，依此类推，在这种策略下，666=100*6 + 50 1 + 10 1 + 51 + 11, 一共用了10张钞票。

这种策略就称为 贪心策略 ：贪心策略是在当前情况下做出最好的选择，根据需要凑出的金额来进行贪心，但是，如果我们换一组钞票面值，比如 1， 5， 11，我们要凑出15的时候， 贪心策略就会出错：

15 = 11 * 1 + 1 * 4 (贪心策略）
15 = 5 * 3（正确策略）
贪心策略哪里出错了？
鼠目寸光

重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？” 接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。　　
那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？
　　
明显 ，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。
依次类推，马上可以知道：如果我们用5来凑出15，cost就是f(10) + 1 = 2 + 1 = 3 。　
　那么，现在w=15的时候，我们该取那种钞票呢？当然是各种方案中，cost值最低的那一个

• 取11：　cost=f(4)+1=4+1=5
• 取5： 　 cost = f(10) + 1 = 2 + 1 = 3
• 取1： 　cost = f(14) + 1 = 4 + 1 = 5
  显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了正确的决策!
  这给了我们一个至关重要的启示—— 只与 相关；更确切地说： f(n) 只与 f(n-1),f(n-5),f(n-11) 相关；更确切地说：
  f(n)=min{f(n-1),f(n-5),f(n-11)}+1

java代码

package coin_change;

public class Solution {
	public int coinChange(int[] coins, int amount) {
		int[] dp = new int[amount + 1];
		for (int i = 0; i <= amount; i++) {
			dp[i] = -1;
		}
		dp[0] = 0;
		// 外层循环金额，内层循环面值
		for (int i = 1; i <= amount; i++) {// 循环各个金额,找到dp[i]最优解
			for (int j = 0; j < coins.length; j++) {// 递推条件
				if (i - coins[j] >= 0 && dp[i - coins[j]] != -1) {
					if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1) {
						dp[i] = dp[i - coins[j]] + 1;
					}
				}
			}
		}
		return dp[amount];
	}

	public static void main(String[] args) {
		Solution solu = new Solution();
		int[] coins = { 1, 2, 5, 7, 10 };
		int amount = 14;
		for (int i = 0; i <= amount; i++) {
			System.out.printf("dp[%d] = %d\n", i, solu.coinChange(coins, i));
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

输出

dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 2
dp[5] = 1
dp[6] = 2
dp[7] = 1
dp[8] = 2
dp[9] = 2
dp[10] = 1
dp[11] = 2
dp[12] = 2
dp[13] = 3
dp[14] = 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

C++代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        std::vector<int> dp;
        for(int i=0;i<=amount;i++){
        	dp.push_back(-1);
        }

        dp[0] = 0;//金额0最优解0
        //外层循环金额，内层循环面值
        for(int i = 1;i<=amount;i++){//循环各个金额,找到dp[i]最优解
            for(int j = 0;j<coins.size();j++){//递推条件
                if(i-coins[j]>=0 && dp[i-coins[j]] != -1){
                    if(dp[i] == -1 || dp[i] > dp[i-coins[j]]+1){
                    	dp[i] = dp[i-coins[j]]+1;
                    }
                }
            }
        }
        return dp[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

说明

这里设置多了一个面值0.
设dp[0] = 0
dp[1] = 1 + dp[0]
dp[2] = 1 + dp[0]
dp[5] = 1 + dp[0]
dp[7] = 1 + dp[0]
dp[10] = 1 + dp[0]

coins = {1,2,5,7,10}
设i代表金额,coins[j]代表第j个面值的金额：
当i-coins[j] >=0且 dp[i-coins[j]] != -1 时：
j = 0,1,2,3,4 ; coins[j] = 1,2,5,7,10
dp[i] = getmin(dp[i - coins[j]]) +1

参考资料

参考–hikes
小象Leecode第九课_动态规划