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
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)
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;
}
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.
Eingabe: n = 3
Ausgabe: 3
Erläuterung: Es gibt drei Möglichkeiten, nach oben zu gelangen.
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.
Eingabe: n = 3
Ausgabe: 3
Erläuterung: Es gibt drei Möglichkeiten, nach oben zu gelangen.
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;
}
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.
Eingabe: Kosten = [1.100,1,1,1.100,1,1.100,1]
Ausgabe: 6
Erläuterung: Sie beginnen bei Index 0.
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`
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!
