LeetCode DayDynamic Programming Teil 5

518. Münzwechsel II

Sie erhalten eine ganzzahlige Array-Münze, die Münzen verschiedener Nennwerte darstellt, und einen ganzzahligen Betrag, der einen Gesamtgeldbetrag darstellt.

Gibt die Anzahl der Kombinationen zurück, aus denen dieser Betrag besteht. Wenn dieser Geldbetrag durch keine Kombination der Münzen gedeckt werden kann, geben Sie 0 zurück.

Sie können davon ausgehen, dass Sie von jeder Münzart unendlich viele haben.

Die Antwort passt garantiert in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiel 1:

Eingabe: Betrag = 5, Münzen = [1,2,5]
Ausgabe: 4
Erläuterung: Es gibt vier Möglichkeiten, den Betrag zusammenzustellen:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Beispiel 2:

Eingabe: Betrag = 3, Münzen = [2]
Ausgabe: 0
Erklärung: Der Betrag von 3 kann nicht nur mit 2er-Münzen gedeckt werden.
Beispiel 3:

Eingabe: Betrag = 10, Münzen = [10]
Ausgabe: 1

Einschränkungen:

1 <= Münzen.Länge <= 300
1 <= Münzen[i] <= 5000
Alle Münzwerte sind einzigartig.
0 <= Betrag <= 5000
Originalseite

    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. Kombinationssumme IV

Geben Sie bei einem Array unterschiedlicher Ganzzahlen und einem ganzzahligen Zielziel die Anzahl der möglichen Kombinationen zurück, die sich zum Ziel addieren.

Die Testfälle werden so generiert, dass die Antwort in eine 32-Bit-Ganzzahl passt.

Beispiel 1:

Eingabe: Nums = [1,2,3], Ziel = 4
Ausgabe: 7
Erklärung:
Die möglichen Kombinationsmöglichkeiten sind:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Beachten Sie, dass unterschiedliche Sequenzen als unterschiedliche Kombinationen gezählt werden.
Beispiel 2:

Eingabe: Nums = [9], Ziel = 3
Ausgabe: 0

Einschränkungen:

1 <= nums.length <= 200
1 <= nums[i] <= 1000
Alle Elemente von Zahlen sind einzigartig.
1 <= Ziel <= 1000

Folge: Was passiert, wenn negative Zahlen im angegebenen Array zulässig sind? Wie verändert es das Problem? Welche Einschränkung müssen wir der Frage hinzufügen, um negative Zahlen zuzulassen?

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

Das obige ist der detaillierte Inhalt vonLeetCode DayDynamic Programming Teil 5. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!