LeetCode OJ 322. Coin Change DP求解

题目链接:https://leetcode.com/problems/coin-change/

322. Coin Change

My Submissions

Question

Total Accepted: 15289 Total
Submissions: 62250 Difficulty: Medium

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.

Credits:

Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Subscribe to 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];
	}
}
时间: 07-08

LeetCode OJ 322. Coin Change DP求解的相关文章

Leetcode OJ --- 322. 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,

Leetcode solution 322: Coin Change

Problem Statement  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 combin

【Leetcode】322. 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,

HDU 2069 Coin Change 母函数求解

HDU 2069 Coin Change 母函数求解 题目:http://acm.hdu.edu.cn/showproblem.php?pid=2069 这题比普通的母函数求解题目复杂一点,多了组成个数的限制, 要求组合个数不能超过 100 个硬币,所以将 c1, c2 定义为二维数组, c1[i][j] 表示 c1[结果][组成该结果的个数] ,然后多了一层遍历个数的循环. // 母函数求解 #include <bits/stdc++.h> using namespace std; cons

322. Coin Change(leetcode )

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,

(Java) LeetCode 322. 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,

[email&#160;protected] [322] Coin Change (Dynamic Programming)

https://leetcode.com/problems/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

322. Coin Change

ref: https://leetcode.com/problems/coin-change/ 就是完全背包问题,可以再复习一遍背包问题. 01背包: for 每一个item for amount...cost[item] f[v] = Max{f[v], f[v-cost[item]] + weight[item]} 因为01背包每个item只能用一次,所以amount要从后往前算,因为比较的时候用的是f[v]和f[v-cost[item]],第二个那里是减号,所以退着算,后面的结果前面没有使

leetcode笔记: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 th