LeetCode Day動的プログラミング パート 5

518. コインチェンジⅡ

さまざまな額面のコインを表す整数配列のコインと、合計金額を表す整数の金額が与えられます。

その量を構成する組み合わせの数を返します。コインのどの組み合わせでもその金額を補えない場合は、0 を返します。

各種類のコインを無限に持っていると想定できます。

答えは符号付き 32 ビット整数に収まることが保証されています。

例 1:

入力: 金額 = 5、コイン = [1,2,5]
出力: 4
説明: 金額を補う方法は 4 つあります:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
例 2:

入力: 金額 = 3、コイン = [2]
出力: 0
説明: 3 の量は、2 のコインだけでは補うことはできません。
例 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. コンビネーションサムⅣ

個別の整数 nums の配列とターゲット整数 target を指定すると、合計が target になる可能な組み合わせの数を返します。

テスト ケースは、答えが 32 ビット整数に収まるように生成されます。

例 1:

入力: 数値 = [1,2,3]、ターゲット = 4
出力: 7
説明:
可能な組み合わせ方法は次のとおりです:
(1、1、1、1)
(1、1、2)
(1、2、1)
(1, 3)
(2、1、1)
(2, 2)
(3, 1)
異なるシーケンスは異なる組み合わせとしてカウントされることに注意してください。
例 2:

入力: 数値 = [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 中国語 Web サイトの他の関連記事を参照してください。