# LeetCode OJ 322. Coin Change DP求解

### 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 = ``, 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

```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;

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];
}
}
```

## 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,

## 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]],第二个那里是减号,所以退着算,后面的结果前面没有使