LeetCode DayDynamic Programming Bahagian 5

518. Tukar Syiling II

Anda diberi syiling susunan integer yang mewakili syiling denominasi berbeza dan jumlah integer mewakili jumlah wang.

Kembalikan bilangan gabungan yang membentuk jumlah itu. Jika jumlah wang itu tidak boleh dibuat dengan sebarang kombinasi syiling, pulangkan 0.

Anda mungkin menganggap bahawa anda mempunyai nombor tidak terhingga bagi setiap jenis syiling.

Jawapannya dijamin sesuai dengan integer 32-bit yang ditandatangani.

Contoh 1:

Input: amaun = 5, syiling = [1,2,5]
Keluaran: 4
Penjelasan: terdapat empat cara untuk membuat jumlah:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Contoh 2:

Input: amaun = 3, syiling = [2]
Output: 0
Penjelasan: jumlah 3 tidak boleh dibuat hanya dengan syiling 2.
Contoh 3:

Input: amaun = 10, syiling = [10]
Keluaran: 1

Kekangan:

1 <= syiling.panjang <= 300
1 <= syiling[i] <= 5000
Semua nilai syiling adalah unik.
0 <= jumlah <= 5000
Halaman Asal

    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. Jumlah Gabungan IV

Memandangkan tatasusunan nombor integer yang berbeza dan sasaran integer sasaran, kembalikan bilangan kemungkinan gabungan yang ditambah kepada sasaran.

Kes ujian dijana supaya jawapan boleh dimuatkan dalam integer 32-bit.

Contoh 1:

Input: angka = [1,2,3], sasaran = 4
Keluaran: 7
Penjelasan:
Cara gabungan yang mungkin adalah:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Ambil perhatian bahawa jujukan berbeza dikira sebagai gabungan berbeza.
Contoh 2:

Input: nums = [9], sasaran = 3
Output: 0

Kekangan:

1 <= nums.length <= 200
1 <= angka[i] <= 1000
Semua elemen nombor adalah unik.
1 <= sasaran <= 1000

Susulan: Bagaimana jika nombor negatif dibenarkan dalam tatasusunan yang diberikan? Bagaimanakah ia mengubah masalah? Apakah had yang perlu kita tambahkan pada soalan untuk membenarkan nombor negatif?

    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];
    }

Atas ialah kandungan terperinci LeetCode DayDynamic Programming Bahagian 5. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!