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中文网其他相关文章！