動的計画は最低硬貨を解決してm元に集める
3526 ワード
322. Coin Change
Question Editorial Solution
My Submissions Total Accepted: 30668 Total Submissions: 120210 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
Example 1: coins =
Example 2: coins =
return
Question Editorial Solution
My Submissions
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
. public class Solution
{
/* m c[1...m] , c[i] i , c[m]
i(1a[j])
{
if(c[i]==0&&c[i-a[j]]!=0)
{
c[i]=c[i-a[j]]+1;
System.out.println("c"+i+":"+c[i]);
}
else
{
if(c[i-a[j]]!=0)
{
c[i]=c[i-a[j]]+1
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
if (dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}