程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode OJ 322. Coin Change DP求解

LeetCode OJ 322. Coin Change DP求解

編輯:關於C++

322. Coin Change

My SubmissionsTotal 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];
	}
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved