509. 斐波那契數列
斐波那契數，通常表示為 F(n)，形成一個序列，稱為斐波那契數列，其中每個數都是前兩個數的和，從 0 和 1 開始。即，
F(0) = 0, F(1) = 1
F(n)=F(n-1)+F(n-2)，對於n＞1 1.
給定 n，計算 F(n)。
範例1：
輸入：n = 2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1.
範例2：
輸入：n = 3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2.
範例 3：
輸入：n = 4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3.
限制：
0
原始頁
遞迴法
public int fib(int n) {
if(n==0){
return 0;
}
else if(n==1){
return 1;
}
else{
return fib(n-1) + fib(n-2);
}
}
登入後複製
遞歸法就像DFS一樣，深入進行，然後回溯得到最終答案。
時間：O(2^n)
空間：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];
}
登入後複製
我們可以使用全域數組來保存結果，以避免相同元素的重複遞歸。例如下圖顯示 f(17) 和 f(18) 是兩種不同的遞迴路線，如果我們使用正常的遞迴方法，我們必須多次計算它們。
時間：O(n)，空間：O(n)
動態規劃
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];
}
登入後複製
遞迴是從上到下再回溯，記憶體遞歸會保存遞迴結果，避免重複計算。現在動態規劃從下到上進行，並將每個步驟的結果儲存到 dp 陣列中。
時間：O(n)
空間：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;
}
登入後複製
70. 爬樓梯
您正在爬樓梯。需要n步才能到達山頂。
每次可以爬 1 或 2 級階梯。您可以透過多少種不同的方式登上頂峰？
範例1：
輸入：n = 2
輸出：2
說明：有兩種方法可以登頂。
- 1 步 + 1 步
- 2步
範例2：
輸入：n = 3
輸出：3
說明：共有三種方法可以登頂。
- 1 步 + 1 步 + 1 步
- 1 步 + 2 步
- 2 步 + 1 步
70. 爬樓梯
您正在爬樓梯。需要n步才能到達山頂。
每次可以爬 1 或 2 級階梯。您可以透過多少種不同的方式登上頂峰？
範例1：
輸入：n = 2
輸出：2
說明：有兩種方法可以登頂。
- 1 步 + 1 步
- 2步
範例2：
輸入：n = 3
輸出：3
說明：共有三種方法可以登頂。
- 1 步 + 1 步 + 1 步
- 1 步 + 2 步
- 2 步 + 1 步
限制：
1
原始頁
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. 最小成本爬樓梯
給定一個整數數組 cost，其中 cost[i] 是樓梯上第 i 步的成本。支付費用後，您可以爬一層或兩層台階。
您可以從索引 0 的步驟開始，也可以從索引 1 的步驟開始。
返回到達樓層頂部的最低成本。
範例1：
輸入：成本 = [10,15,20]
輸出：15
說明：您將從索引 1 開始。
- 支付 15 美元，爬兩個台階即可到達頂部。
總成本為15。
範例2：
輸入：成本 = [1,100,1,1,1,100,1,1,100,1]
輸出：6
說明：您將從索引 0 開始。
- 支付 1 並爬兩個階梯即可到達索引 2。
- 支付 1 並爬兩個階梯即可到達索引 4。
- 支付 1 並爬兩個階梯即可到達索引 6。
- 支付 1 並爬一級即可達到指數 7。
- 支付 1 並爬兩個階梯即可到達索引 9。
- 支付1並爬一級即可到達頂部。
總費用是6。
限制：
2
0
原始頁
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`
登入後複製
請注意，問題告訴我們可以從索引0 和索引1 開始，這意味著如果樓梯數小於2，我們的成本將為0，因為我們可以從該點開始，並且start 的行為將成本為0，只有移動成本的行為。
以上是LeetCode Day動態程式設計第1部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！
