Coin Change

發表於   |   分類於

Coin Change

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.

有向无环图上的最短路问题：给定一个出发点，求它到所有叶子节点的路径中最短的那条路径的长度。

AC代码：

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
32
33
34
35
36
37
38
class Solution {

public:

	int solve(int rest,vector<int>& coins, int amount, vector<int>& DP)
	{
		if (rest == 0) return 0;
		if (rest < 0) return amount+1;

		if (DP[rest] >= 0) return DP[rest];

		int r = amount + 1;

		for (int i = 0; i < coins.size(); ++i)
		{
			int s = solve(rest - coins[i], coins, amount, DP) + 1;
			if (s < r) r = s;
		}

		DP[rest] = r;

		return r;
	}

	int coinChange(vector<int>& coins, int amount) {

		if (0 == amount) return 0;
		if (0 == coins.size()) return -1;

		vector<int> DP(amount+1,-1);

		int r = solve(amount,coins,amount,DP);

		if (r > amount) return -1;

		return r;
	}
};

非递归形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		if (0 == amount) return 0;
		if (0 == coins.size()) return -1;

		vector<int> DP(amount + 1, INT_MAX);
		DP[0] = 0;

		for (int i = 0; i < coins.size(); ++i)
		{
			for (int j = 1; j <= amount ; ++j)
			{
				if (j >= coins[i] && DP[j - coins[i]] != INT_MAX)
				{
					DP[j] = min(DP[j], DP[j-coins[i]]+1);
				}
			}
		}

		if (DP[amount] > amount) return -1;
		return DP[amount];
	}
};