LeetCode Day動態程式設計第 5 部分

518. 硬幣找零 II

給你一個代表不同面額硬幣的整數陣列硬幣和代表總金額的整數金額。

傳回組成該金額的組合數。如果任何硬幣組合都無法彌補該金額，則返回 0。

您可以假設您擁有無限數量的每種硬幣。

答案保證適合有符號的 32 位元整數。

範例1：

輸入：金額= 5，硬幣= [1,2,5]
輸出：4
說明：補金額有四種方式：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
範例2：

輸入：金額 = 3，硬幣 = [2]
輸出：0
說明：僅用2枚硬幣無法湊足3枚。
範例 3：

輸入：金額 = 10，金幣 = [10]
輸出：1

限制：

1 1 所有硬幣的價值都是獨一無二的。
0 原始頁

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

            }
        }
                    // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[coins.length][amount];
    }

    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++){
                dp[j] = dp[j] + dp[j-coins[i]];
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[amount];
    }

377. 組合總和 IV

給定一個由不同整數 nums 組成的陣列和一個目標整數 target，傳回加起來達到 target 的可能組合數。

產生測試案例，以便答案可以適合 32 位元整數。

範例1：

輸入：nums = [1,2,3]，target = 4
輸出：7
說明：
可能的組合方式有：
(1, 1, 1, 1)
(1, 1, 2)
(1,2,1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
請注意，不同的序列被視為不同的組合。
範例2：

輸入：nums = [9]，目標 = 3
輸出：0

限制：

1 1 nums 的所有元素都是唯一的。
1

後續：如果給定數組中允許負數怎麼辦？它如何改變問題？我們需要在問題中增加什麼限制才能允許負數？

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i=1; i<=target; i++){
            for(int j=0; j<nums.length; j++){
                if(nums[j] <= i){
                    dp[i] = dp[i] + dp[i-nums[j]];
                }
            }
            // System.out.println(Arrays.toString(dp));
        }
        return dp[target];
    }

以上是LeetCode Day動態程式設計第 5 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！