Programmation dynamique LeetCode Day, partie 5

518. Changement de pièces II

Vous recevez un tableau de pièces entières représentant des pièces de différentes dénominations et un montant entier représentant une somme d'argent totale.

Renvoyer le nombre de combinaisons qui composent ce montant. Si cette somme d'argent ne peut être compensée par aucune combinaison de pièces, renvoyez 0.

Vous pouvez supposer que vous possédez un nombre infini de chaque type de pièce.

Il est garanti que la réponse s'inscrit dans un entier signé de 32 bits.

Exemple 1 :

Entrée : montant = 5, pièces = [1,2,5]
Sortie : 4
Explication : il existe quatre façons de reconstituer le montant :
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Exemple 2 :

Entrée : montant = 3, pièces = [2]
Sortie : 0
Explication : le montant de 3 ne peut pas être compensé uniquement avec des pièces de 2.
Exemple 3 :

Entrée : montant = 10, pièces = [10]
Sortie : 1

Contraintes :

1 <= coins.length <= 300
1 <= pièces[i] <= 5000
Toutes les valeurs des pièces sont uniques.
0 <= montant <= 5000
Page originale

    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. Somme combinée IV

Étant donné un tableau de nombres entiers distincts et une cible entière cible, renvoie le nombre de combinaisons possibles qui totalisent la cible.

Les cas de test sont générés de manière à ce que la réponse puisse tenir dans un entier de 32 bits.

Exemple 1 :

Entrée : nums = [1,2,3], cible = 4
Sortie : 7
Explication :
Les combinaisons possibles sont :
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Notez que différentes séquences sont comptées comme différentes combinaisons.
Exemple 2 :

Entrée : nums = [9], cible = 3
Sortie : 0

Contraintes :

1 <= nums.length <= 200
1 <= nums[i] <= 1000
Tous les éléments des nums sont uniques.
1 <= cible <= 1000

Suivi : que se passe-t-il si les nombres négatifs sont autorisés dans le tableau donné ? En quoi cela change-t-il le problème ? Quelle limitation devons-nous ajouter à la question pour autoriser les nombres négatifs ?

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!