LeetCode OJ 322. Coin Change DP求解

322. Coin Change

My SubmissionsQuestionTotal Accepted:15289Total Submissions:62250Difficulty:Medium

You are given coins of different denominations and a total amount of moneyamount. 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
return3(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.

Credits:
Special thanks [email protected] adding this problem and creating all test cases.

Subscribeto see which companies asked this question

Show Tags Have you met this question in a real interview? Yes No  

Discuss

給定幾個固定面值的硬幣，可以無限使用。一個目標數，要求用最少的硬幣兌換這個target。

換一種思路理解題目，每次可以走給定面值的步數，問最少走多少步能達到目標。如此一來便可以用BFS求解。

第二種解法是DP，dp[i] = min {dp[i - a], dp[i - b], dp[i - c] ...... }。動態規劃只要有公式就能很快求解。

我用DP求解的AC代碼

 

package march;

import java.util.Arrays;

/**
 * @auther lvsheng
 * @date 2016年3月16日
 * @time 下午11:20:44
 * @project LeetCodeOJ
 * 
 */

public class CoinChange {
	public static void main(String[] args) {
		int[] a = { 1, 2, 5 };
		System.out.println(coinChange(a, 11));
		int[] b = { 2 };
		System.out.println(coinChange(b, 3));
	}

	public static int coinChange(int[] coins, int amount) {
		int len = coins.length;
		if (len == 0) return -1;
		int[] dp = new int[amount + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;

		Arrays.sort(coins);

		for (int i = 0; i < len && coins[i] <= amount; i++) dp[coins[i]] = 1;

		for (int i = 1; i <= amount; i++) {
			int min = dp[i];
			if (min == 1) continue;
			for (int j = 0; j < len && coins[j] < i; j++) {
				int c = coins[j];
				int d = dp[i - c];
				if (d != Integer.MAX_VALUE && d < min) min = d + 1;
			}
			dp[i] = min;
		}

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