LeetCode DayDynamische Programmierung Teil1

509. Fibonacci-Zahl

Die Fibonacci-Zahlen, allgemein als F(n) bezeichnet, bilden eine Folge, die Fibonacci-Folge genannt wird, sodass jede Zahl die Summe der beiden vorhergehenden ist, beginnend bei 0 und 1. Das heißt,

F(0) = 0, F(1) = 1
F(n) = F(n – 1) + F(n – 2), für n > 1.
Berechnen Sie bei gegebenem n F(n).

Beispiel 1:

Eingabe: n = 2
Ausgabe: 1
Erklärung: F(2) = F(1) + F(0) = 1 + 0 = 1.
Beispiel 2:

Eingabe: n = 3
Ausgabe: 2
Erklärung: F(3) = F(2) + F(1) = 1 + 1 = 2.
Beispiel 3:

Eingabe: n = 4
Ausgabe: 3
Erklärung: F(4) = F(3) + F(2) = 2 + 1 = 3.

Einschränkungen:

0 <= n <= 30
Originalseite

Rekursionsmethode

    public int fib(int n) {
        if(n==0){
            return 0;
        }     
        else if(n==1){
            return 1;
        }   
        else{
            return fib(n-1) + fib(n-2);
        }
    }

Die Rekursionsmethode ist wie DFS, um in die Tiefe zu gehen und dann das Backtracking durchzuführen, um die endgültige Antwort zu erhalten.
Zeit: O(2^n)
Leerzeichen: O(1)

    private int[] dp = new int[31];
    public int fib(int n) {
        if(n<2){
            dp[n] = n;
            return n;
        }  

        if(n>=2 && dp[n]!=0){
            return dp[n];
        }

        dp[n] = fib(n-1) + fib(n-2);
        return dp[n];
    }




</p>
<p>Wir können ein globales Array verwenden, um das Ergebnis zu speichern und eine erneute Rekursion derselben Elemente zu vermeiden. z.B. Die Abbildung unten zeigt, dass f(17) und f(18) zwei verschiedene Rekursionsrouten sind und wenn wir die normale Rekursionsmethode verwenden, müssen wir sie mehr als einmal berechnen. </p>

<p><img src="https://img.php.cn/upload/article/000/000/000/172127798860260.png" alt="Image description" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<p>Zeit: O(n), Raum: O(n)</p>

<h2>
  
  
  Dynamische Programmierung
</h2>



<pre class="brush:php;toolbar:false">    public int fib(int n) {
        if(n<2){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

Die Rekursion funktioniert von oben nach unten und beim Zurückverfolgen speichert die Speicherrekursion die Rekursionsergebnisse, um Doppelberechnungen zu vermeiden. Jetzt arbeitet die dynamische Programmierung von unten nach oben und speichert das Ergebnis jedes Schritts im dp-Array.
Zeit: O(n)
Leerzeichen: O(n)

Außerdem können wir die Grenzwertanzahl anstelle eines Arrays dynamisch aktualisieren. Dies spart Platzkomplexität, insbesondere bei einer großen Anzahl von Elementen.

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int start = 0;
        int pre = 1;
        int res = pre;

        for(int i=2; i<=n; i++){
            res = start + pre;
            start = pre;
            pre = res;
        }
        return res;
    }

70. Treppensteigen

Sie steigen eine Treppe hinauf. Es sind n Schritte erforderlich, um die Spitze zu erreichen.

Jedes Mal können Sie entweder 1 oder 2 Stufen hinaufsteigen. Auf wie viele verschiedene Arten kann man den Gipfel erklimmen?

Beispiel 1:

Eingabe: n = 2
Ausgabe: 2
Erläuterung: Es gibt zwei Möglichkeiten, nach oben zu gelangen.

1. 1 Schritt + 1 Schritt
2. 2 Schritte Beispiel 2:

Eingabe: n = 3
Ausgabe: 3
Erläuterung: Es gibt drei Möglichkeiten, nach oben zu gelangen.

1. 1 Schritt + 1 Schritt + 1 Schritt
2. 1 Schritt + 2 Schritte
3. 2 Schritte + 1 Schritt

70. Treppensteigen

Sie steigen eine Treppe hinauf. Es dauert n Schritte, um die Spitze zu erreichen.

Jedes Mal können Sie entweder 1 oder 2 Stufen hinaufsteigen. Auf wie viele verschiedene Arten kann man den Gipfel erklimmen?

Beispiel 1:

Eingabe: n = 2
Ausgabe: 2
Erläuterung: Es gibt zwei Möglichkeiten, nach oben zu gelangen.

1. 1 Schritt + 1 Schritt
2. 2 Schritte Beispiel 2:

Eingabe: n = 3
Ausgabe: 3
Erläuterung: Es gibt drei Möglichkeiten, nach oben zu gelangen.

1. 1 Schritt + 1 Schritt + 1 Schritt
2. 1 Schritt + 2 Schritte
3. 2 Schritte + 1 Schritt

Einschränkungen:

1 <= n <= 45
Originalseite

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        } 
        return dp[n];       
    }

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }

        int prepre = 1;
        int pre = 2;
        int res = 0;
        for(int i=3; i<=n; i++){
            res = prepre + pre;
            prepre = pre;
            pre = res;
        } 
        return res;       
    }

746. Mindestkosten beim Treppensteigen

Sie erhalten ein ganzzahliges Array „Kosten“, wobei „Kosten[i]“ die Kosten der i-ten Stufe auf einer Treppe sind. Sobald Sie die Kosten bezahlt haben, können Sie entweder eine oder zwei Stufen hinaufsteigen.

Sie können entweder mit dem Schritt mit Index 0 oder mit dem Schritt mit Index 1 beginnen.

Geben Sie die Mindestkosten zurück, um die Oberkante der Etage zu erreichen.

Beispiel 1:

Eingabe: Kosten = [10,15,20]
Ausgabe: 15
Erläuterung: Sie beginnen bei Index 1.

• Zahlen Sie 15 und steigen Sie zwei Stufen hinauf, um den Gipfel zu erreichen. Die Gesamtkosten betragen 15. Beispiel 2:

Eingabe: Kosten = [1.100,1,1,1.100,1,1.100,1]
Ausgabe: 6
Erläuterung: Sie beginnen bei Index 0.

• Zahlen Sie 1 und steigen Sie zwei Stufen hinauf, um Index 2 zu erreichen.
• Zahlen Sie 1 und steigen Sie zwei Stufen hinauf, um Index 4 zu erreichen.
• Zahlen Sie 1 und steigen Sie zwei Stufen hinauf, um Index 6 zu erreichen.
• Zahlen Sie 1 und steigen Sie eine Stufe hinauf, um Index 7 zu erreichen.
• Zahlen Sie 1 und steigen Sie zwei Stufen hinauf, um Index 9 zu erreichen.
• Zahlen Sie 1 und steigen Sie eine Stufe hinauf, um die Spitze zu erreichen. Die Gesamtkosten betragen 6,

Einschränkungen:

2 <= cost.length <= 1000
0 <= Kosten[i] <= 999
Originalseite

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length < 2){
            return 0;
        }

        int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[dp.length-1];

    }
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`

Seien Sie vorsichtig, denn die Frage hat uns gesagt, dass wir mit Index 0 und Index 1 beginnen können, was bedeutet, dass wir 0 kosten, wenn die Anzahl der Treppen weniger als 2 beträgt, da wir an diesem Punkt beginnen können und das Startverhalten wird Kosten 0, nur das Verhalten der Umzugskosten.

Das obige ist der detaillierte Inhalt vonLeetCode DayDynamische Programmierung Teil1. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!