Java実装LeetCode 518.小銭両替II(ダイナミックプランニング)

異なる額面のコインと総額を指定します.関数を書き出して総額にまとめることができるコインの組み合わせ数を計算します.各額面のコインに無限があると仮定します.
例1:
入力:amount=5,coins=[1,2,5]出力:4解釈:合計金額にまとめるには4つの方法がある:5=5=2+2+15=2+1+15=1+1+1+1+1+1の例2:
入力:amount=3,coins=[2]出力:0解釈:額面2の硬貨だけで総額3にまとめることはできません.例3:
入力:amount=10、coins=[10]出力:1
注意:
次のように仮定できます.
0<=amount(総金額)<=5000 1<=coin(硬貨額面)<=5000硬貨種500種を超えない結果32ビット符号整数に合致
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/coin-change-2著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
【小銭両替】という問題では、amountを集める最小硬貨の数を見つけるという小さな変更が行われています.この問題はamountを集めるすべての組合せ数を見つけることです.基礎フレームワークは同じですが、すべてのdp要素を初期化しないだけで、dp[0]=1、前回できる数を加算すればいいです.

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
		for(int i = 0; i < coins.length; i++) {
			for(int j = coins[i]; j <= amount; j++) {
				if(j >= coins[i]) {
					dp[j] += dp[j-coins[i]];
				}
			}
		}
		return dp[amount];
    }
}