Leetcodeブラシ問題javaの322.小銭両替

実行結果:
に合格
詳細を表示
実行時間:13 ms、すべてのJavaコミットで68.96%のユーザーを破った
メモリ消費量:35.9 MB、すべてのJavaコミットで51.50%のユーザーを破った
タイトル:
異なる額面のコインcoinsと総金額amountを与えます.合計金額にまとめるのに必要な最小限のコイン数を計算する関数を作成します.合計金額を構成できるコインの組み合わせがない場合は、-1を返します.
例1:
入力:coins=[1,2,5],amount=11出力:3  11=5+5+5+1
例2:
入力:coins=[2]、amount=3出力:-1
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/coin-change 著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:
ダイナミックプランニング、この問題は完全二乗に似ています.https://blog.csdn.net/qq_41901915/article/details/104232810
この問題の難点は存在しない時にどのように処理するかで、存在しない時、ずっと前にさかのぼって、ずっと前に減らして、マイナス数まで.存在すると0まで減算されます
コード:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        //      amount+1，      
        Arrays.fill(dp,amount+1);
        //        
        dp[0]=0;
        for(int i=1;i<=amount;i++)
        {
            for(int j=0;j=0)
                {
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
}