509.斐波那契數(shù)列

斐波那契數(shù) （通常用 F(n) 表示）形成的序列稱為 斐波那契數(shù)列 。該數(shù)列由 0 和 1 開始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定 n ，請計(jì)算 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 <= n <= 30

思路：動(dòng)規(guī)五步

確定dp數(shù)組和數(shù)組下標(biāo)含義

DP題目都需要定義一維或者二維的狀態(tài)轉(zhuǎn)移數(shù)組，通常是叫dp。

本題中，dp[i]表示第i個(gè)斐波那契數(shù)的數(shù)值為dp[i]

遞推公式

本題是比較簡單的DP題目，就是因?yàn)轭}目描述中已經(jīng)把遞推公式告訴我們了。

遞推公式：dp[i]=dp[i-1]+dp[i-2]

DP數(shù)組初始化

題目描述已經(jīng)說了，dp[0]=1

遍歷順序

因?yàn)閐p[i]是由dp[i-1]和dp[i-2]得到的，因此需要從前往后遍歷，才能保證每次dp[i]能夠考慮到前面的兩個(gè)元素。

打印DP數(shù)組

這一步主要用于debug，打印出來看看和想象的是否一樣

完整版

class Solution {
public:
    int fib(int n) {
        if(n==0) 
            return 0;
        if(n==1) 
            return 1;
        //建立dp數(shù)組
        vector<int>dp(n+1);
        //dp數(shù)組初始化，初始化依賴于遞推公式
        //注意這里初始化需要放到if特殊情況后面，因?yàn)槿绻鹡是0，就不存在dp[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];
    }
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

debug測試

這段代碼的問題出在沒有處理 n 為 0 或 1 的情況。如果 n 為 0，那么 dp[1] 就不存在，這時(shí)試圖訪問 dp[1] 會導(dǎo)致溢出。

dp[0]=0;dp[1]=1;if特殊情況需要放最前面，因?yàn)槿绻鹡是0，就不存在dp[1]

修改加上if條件之后通過。

空間復(fù)雜度優(yōu)化版

• 實(shí)際上，我們只需要維護(hù)兩個(gè)數(shù)值就可以了，不需要記錄整個(gè)序列。

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

優(yōu)化思路

斐波那契數(shù)列的定義：F(0) = 0，F(xiàn)(1) = 1，F(xiàn)(n) = F(n-1) + F(n-2) 對于所有 n >= 2。這意味著，要計(jì)算第 n 個(gè)斐波那契數(shù)，只需要知道前兩個(gè)斐波那契數(shù)，即 F(n-1) 和 F(n-2)。

優(yōu)化版本的斐波那契數(shù)列計(jì)算利用了這個(gè)性質(zhì)。在循環(huán)開始時(shí)，dp[0] 和 dp[1] 分別存儲 F(n-2) 和 F(n-1)。然后，我們計(jì)算新的斐波那契數(shù) F(n) = dp[0] + dp[1]，并更新 dp[0] 和 dp[1]，以備下一個(gè)循環(huán)使用。所以，我們只需要兩個(gè)變量就可以計(jì)算出斐波那契數(shù)列的下一個(gè)值，而不必維護(hù)整個(gè)數(shù)列。

這樣的優(yōu)化實(shí)際上是一個(gè)空間優(yōu)化，稱為 “滾動(dòng)數(shù)組” 或者 “滑動(dòng)窗口” 的策略。其基本思想是只保存當(dāng)前階段需要的數(shù)據(jù)，淘汰過去不再需要的數(shù)據(jù)，避免存儲不必要的信息，從而降低空間復(fù)雜度。

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

70.爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個(gè)臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示：

• 1 <= n <= 45

思路

一共n階臺階，1階：1步，2階：2種（2或者1+1），3階：3種（2+1或1+2或1+1+1）4階：5種。

我們可以發(fā)現(xiàn)，3階，只能從1階和2階邁上來，實(shí)際上就是1階的1種方法加上2階的2種方法。

而4階，只能從2階和3階邁上來，因此登上4階的方法數(shù)就是登上2階的方法數(shù)+登上3階的方法數(shù)，2+3=5種。

我們此時(shí)就可以發(fā)現(xiàn)遞推關(guān)系，也就是當(dāng)前階梯的狀態(tài)，依賴于他的前兩個(gè)階梯的狀態(tài)。（一次性最多邁兩步）

也就是說，因?yàn)槊看沃荒芘?1 級或 2級，所以f(x)的數(shù)值只能從f(x-1)和f(x-2)轉(zhuǎn)移過來。而這里要統(tǒng)計(jì)方案總數(shù)，我們就需要對這兩項(xiàng)的貢獻(xiàn)求和。

DP數(shù)組的含義以及下標(biāo)含義

dp[i]：達(dá)到第i階，有dp[i]種方法。

后面的推導(dǎo)都是基于含義

遞推公式

dp[i]=dp[i-1]+dp[i-2]，其中dp[i-1]表示達(dá)到第i-1階有多少種方法，dp[i-2]同理

DP數(shù)組初始化

首先因?yàn)轭}目描述達(dá)到第一階有1種方法第二階有2種，所以dp[1]=1,dp[2]=2.

dp[0]的含義是，達(dá)到第0階需要多少種方法。但是本題中，dp[0]是沒有意義的！因?yàn)轭}目給出的數(shù)據(jù)范圍，n是一個(gè)>=1的正整數(shù)，因此我們完全不需要考慮dp[0]的情況，也不需要像題解一樣令dp[0]=1，因?yàn)闆]有意義。

遍歷順序

遍歷順序一定是從前往后，因?yàn)楸绢}也屬于斐波那契數(shù)列題目，當(dāng)前值基于他的前兩個(gè)狀態(tài)。

打印DP數(shù)組

我們可以先推導(dǎo)自己認(rèn)為的DP數(shù)組數(shù)值，然后打印看是否符合要求。

完整版

• 本題也是一道斐波那契數(shù)列的相關(guān)題目

class Solution {
public:
    int climbStairs(int n) {
        if(n<=2) return n;
        vector<int>dp(n+1,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];
    }
};

debug測試

Line 1034: Char 34: runtime error: applying non-zero offset 4 to null pointer (stl_vector.h)

這個(gè)錯(cuò)誤信息是說試圖對一個(gè)空的vector應(yīng)用非零的偏移量。這個(gè)問題出在使用 dp[i] 之前沒有為 dp 分配足夠的空間。

在C++中， std::vector 的初始大小為0，如果試圖訪問或修改不存在的元素（如 dp[1] 或 dp[2]），這就會導(dǎo)致運(yùn)行時(shí)錯(cuò)誤。

需要先調(diào)用 std::vector::resize 或者在創(chuàng)建 std::vector 時(shí)就指定它的大小，才能保證有足夠的空間來存儲元素。

修改dp初始化：vector<int>dp(n+1,0)

空間復(fù)雜度優(yōu)化寫法

• 很多動(dòng)規(guī)的題目其實(shí)都是當(dāng)前狀態(tài)依賴前兩個(gè)，或者前三個(gè)狀態(tài)，都可以做空間上的優(yōu)化，但面試中能寫出版本一就夠了，清晰明了，如果面試官要求進(jìn)一步優(yōu)化空間的話，我們再去優(yōu)化。
• 因?yàn)榘姹疽徊拍荏w現(xiàn)出動(dòng)規(guī)的思想精髓，遞推的狀態(tài)變化、

// 版本二
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};

746.使用最小花費(fèi)爬樓梯

給你一個(gè)整數(shù)數(shù)組 cost ，其中 cost[i] 是從樓梯第 i 個(gè)臺階向上爬需要支付的費(fèi)用。一旦你支付此費(fèi)用，即可選擇向上爬一個(gè)或者兩個(gè)臺階。

你可以選擇從下標(biāo)為 0 或下標(biāo)為 1 的臺階開始爬樓梯。

請你計(jì)算并返回達(dá)到樓梯頂部的最低花費(fèi)。

示例 1：

輸入：cost = [10,15,20]
輸出：15
解釋：你將從下標(biāo)為 1 的臺階開始。

- 支付 15 ，向上爬兩個(gè)臺階，到達(dá)樓梯頂部。
  總花費(fèi)為 15 。

示例 2：

輸入：cost = [1,100,1,1,1,100,1,1,100,1]
輸出：6
解釋：你將從下標(biāo)為 0 的臺階開始。

- 支付 1 ，向上爬兩個(gè)臺階，到達(dá)下標(biāo)為 2 的臺階。
- 支付 1 ，向上爬兩個(gè)臺階，到達(dá)下標(biāo)為 4 的臺階。
- 支付 1 ，向上爬兩個(gè)臺階，到達(dá)下標(biāo)為 6 的臺階。
- 支付 1 ，向上爬一個(gè)臺階，到達(dá)下標(biāo)為 7 的臺階。
- 支付 1 ，向上爬兩個(gè)臺階，到達(dá)下標(biāo)為 9 的臺階。
- 支付 1 ，向上爬一個(gè)臺階，到達(dá)樓梯頂部。
  總花費(fèi)為 6 。

提示：

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

思路

本題首先要明確題意。題目中沒有給出樓頂?shù)奈恢?，但?strong>樓頂?shù)碾A數(shù)應(yīng)該是cost.size()而不是cost數(shù)組的最大下標(biāo)。題意如下圖所示。

可以選擇0或者1往上跳，每次往上跳都花費(fèi)cost[i]的體力。

DP數(shù)組含義

我們要求的是到達(dá)樓頂?shù)?strong>最小花費(fèi)，dp[i]表示的就是花費(fèi)。

i表示的是當(dāng)前到了哪個(gè)臺階，而dp[i]的值表示的就是到i位置時(shí)候的所有花費(fèi)

DP數(shù)組含義一定要搞清楚，這一點(diǎn)很重要，遞推公式基于數(shù)組

遞推公式

遞推公式我們需要得到的是dp[i]。本題可以一步一個(gè)臺階或者一步兩個(gè)臺階，因此，dp[i]是由dp[i-1]或者dp[i-2]跳上來的。

dp[i]表示的是，跳到i位置所需要的最小花費(fèi)。因?yàn)榧瓤梢詮膇-1跳上來，也可以從i-2，因此遞推就是取這二者花費(fèi)的最小值。公式推導(dǎo)如下圖：

因此公式為，dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。

DP數(shù)組初始化

dp公式可以看出，最開始的dp[2]是由dp[1]和dp[0]求得。也就是說我們只需要初始化dp[1]和dp[0]。

因?yàn)?和1是初始值，往上跳的時(shí)候才需要花費(fèi)體力值，因此dp[0]和dp[1]的值都是0.

（DP數(shù)組的含義：dp[i]表示的是跳到i時(shí)候的花費(fèi)，初始值花費(fèi)就是0）

遍歷順序

本題也是爬樓梯的衍生題目，因此也是從前到后遍歷。

遍歷順序補(bǔ)充

但是稍稍有點(diǎn)難度的動(dòng)態(tài)規(guī)劃，其遍歷順序并不容易確定下來。 例如：01背包，都知道兩個(gè)for循環(huán)，一個(gè)for遍歷物品，嵌套一個(gè)for遍歷背包容量，那么，為什么不是一個(gè)for遍歷背包容量，嵌套一個(gè)for遍歷物品呢？ 以及在使用一維dp數(shù)組的時(shí)候遍歷背包容量為什么要倒序呢？

這些問題都是和遍歷順序有關(guān)的，等學(xué)到了背包再進(jìn)行對比。

打印DP數(shù)組

debug過程中如果出現(xiàn)問題，就把預(yù)期DP數(shù)組寫出，再打印進(jìn)行對比。

預(yù)期DP數(shù)組：

文章來源地址http://www.zghlxwxcb.cn/news/detail-542776.html

完整版

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if(cost.size()<=1) return 0;
        int n=cost.size();
        //初始化
        vector<int>dp(n+1,0);
        //dp[0]=0;已經(jīng)進(jìn)行了0的初始化這兩句可以不寫
        //dp[1]=0;
        for(int i=2;i<=n;i++){
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

空間復(fù)雜度優(yōu)化寫法

// 版本二
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = 0;
        int dp1 = 0;
        for (int i = 2; i <= cost.size(); i++) {
            int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
            dp0 = dp1; // 記錄一下前兩位
            dp1 = dpi;
        }
        return dp1;
    }
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

• 在面試中，能寫出版本一就行，除非面試官額外要求 空間復(fù)雜度，那么再去思考版本二，因?yàn)榘姹径€是有點(diǎn)繞。版本一才是正常思路。

到了這里，關(guān)于DAY42：動(dòng)態(tài)規(guī)劃（二）斐波那契數(shù)列+爬樓梯+最小花費(fèi)爬樓梯的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！