給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回?-1。

示例?1:

輸入: coins = [1, 2, 5], amount = 11
輸出: 3?
解釋: 11 = 5 + 5 + 1
示例 2:

輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認為每種硬幣的數量是無限的。

思路：每一個數據都可以看做前面某一個dp[x]加上一個coins[i]的值，如果找不到這樣的數字，那說明無法進行兌換

提交的代碼:

class Solution {
? ? public int coinChange(int[] coins, int amount) {
? ? ?int i,j;
?? ??? ?Arrays.sort(coins);
? ? ? ? int n = coins.length;
? ? ? ? int[] dp = new int[amount+1];
? ? ? ? int min = Integer.MAX_VALUE;
? ? ? ? dp[0] = 0;
? ? ? ? if(amount==0)
? ? ? ? {
? ? ? ? ?? ?return 0;
? ? ? ? }
? ? ? ? for(i=1;i<=amount;i++)
? ? ? ? {
? ? ? ? ?? ?min = Integer.MAX_VALUE;
? ? ? ? ?? ?for(j=0;j<n;j++)
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?if(i-coins[j]>=0)
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?if(dp[i-coins[j]] != Integer.MAX_VALUE)
? ? ? ? ?? ??? ??? ?{
? ? ? ? ? ? ?? ??? ??? ?min = java.lang.Math.min(min, dp[i-coins[j]]+1);
? ? ? ? ?? ??? ??? ?}

? ? ? ? ?? ??? ?}
? ? ? ? ?? ??? ?else
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?break;
? ? ? ? ?? ??? ?}
? ? ? ? ?? ?}
? ? ? ? ?? ?dp[i] = min;
? ? ? ? }
? ? ? ? if(dp[amount]!=Integer.MAX_VALUE)
? ? ? ? {
? ? ? ? ?? ? return dp[amount];
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ?? ?return -1;
? ? ? ? }
? ? }
}

完整的代碼：

import java.util.Arrays;

public class Solution322 {
?? ?public static int coinChange(int[] coins, int amount) {
?? ??? ?int i,j;
?? ??? ?Arrays.sort(coins);
? ? ? ? int n = coins.length;
? ? ? ? int[] dp = new int[amount+1];
? ? ? ? int min = Integer.MAX_VALUE;
? ? ? ? dp[0] = 0;
? ? ? ? if(amount==0)
? ? ? ? {
? ? ? ? ?? ?return 0;
? ? ? ? }
? ? ? ? for(i=1;i<=amount;i++)
? ? ? ? {
? ? ? ? ?? ?min = Integer.MAX_VALUE;
? ? ? ? ?? ?for(j=0;j<n;j++)
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?if(i-coins[j]>=0)
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?if(dp[i-coins[j]] != Integer.MAX_VALUE)
? ? ? ? ?? ??? ??? ?{
? ? ? ? ? ? ?? ??? ??? ?min = java.lang.Math.min(min, dp[i-coins[j]]+1);
? ? ? ? ?? ??? ??? ?}

? ? ? ? ?? ??? ?}
? ? ? ? ?? ??? ?else
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?break;
? ? ? ? ?? ??? ?}
? ? ? ? ?? ?}
? ? ? ? ?? ?dp[i] = min;
? ? ? ? }
? ? ? ? if(dp[amount]!=Integer.MAX_VALUE)
? ? ? ? {
? ? ? ? ?? ? return dp[amount];
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ?? ?return -1;
? ? ? ? }
? ? }
?? ?public static void main(String[] args)
?? ?{
?? ??? ?int[] coins = {186,419,83,408};
?? ??? ?int amount = 6249;
?? ??? ?System.out.println(coinChange(coins,amount));
?? ?}
}
?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Leetcode--322. 零钱兑换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。