Leetcode 518. Coin Change 2

tags: Leetcode(JAVA)

題目 : https://leetcode.com/problems/coin-change-2/ 。

想法 :

​​​​無窮背包問題。

時間複雜度 : O(n*m)。

程式碼 : (JAVA)

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp=new int[10010];
        
        for(int i=0 ; i<=amount ; i++){
            dp[i]=0;
        }
        
        dp[0]=1;
        for(int i=0 ; i<coins.length ; i++){
            for(int j=coins[i] ; j<=amount ; j++){
                dp[j] += dp[j - coins[i]];
            }
            //System.out.printf("%d %d\n", i, dp[i]);
        }
        
        return dp[amount];
    }
}