动态规划方法以及例题（斐波那契数列，爬楼梯）

本是古典何须时尚 2023-10-06 18:49 34阅读 0赞

## 动态规划方法以及例题（斐波那契数列，爬楼梯） ##

## 以下内容是本人学习大佬 代码随想录 up主的笔记内容。大家可以看看大佬的[代码随想录博客][Link 1] ##

做动规题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目做过之后，都不太清楚dp\[i\]表示的是什么。

这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后看题解，然后继续照葫芦画瓢陷入这种恶性循环中。状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

### 方法： ###

1.  确定dp数组（dp\[ \]）以及下标的含义
2.  确定递推公式
3.  dp数组如何初始化
4.  确定遍历顺序
5.  举例推导dp数组

### 例题： ###

#### 斐波那契数列问题 ####

题目：斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字

都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1，F(n) = F(n - 1) + F(n - 2)，其中 n > 1给你n ，请计算 F(n) 。

注意：0 <= n <= 30。

相信这道题目很多小伙伴都做过，可能当时的你们并不知道这道题用的是动态规划，现在就一起来康康。

1.  确定dp数组(即F(n)数组)以及下标的含义dp\[i\]：数到第i个数，dp\[i\]是它的值。
2.  递推公式题目已经给出，省得我们想。
3.  题目给出F(0) = 0，F(1) = 1。已经够了。
4.  根据递推式可知：是从前往后递推的。
5.  当n=5时，F(n)=5。验证结果是否一致。

代码如下：

#include<iostream>
    #include<vector>
    using namespace std;
    int main()
    {
        
        int n;
        cin>>n;
        vector<int>dp(n+1);
        if(n<=1)cout<<"n";
        else
        {
        
            dp[0]=0;
            dp[1]=1;
            for(int i=2; i<=n; i++)
            {
        
                dp[i]=dp[i-1]+dp[i-2];
            }
            cout<<dp[n];
        }
    }

时间复杂度：O(n)，空间复杂度：O(n)。

运行结果：  
![在这里插入图片描述][0d36f68b29c347229ffb46a2bd975812.png_pic_center]

#### 爬楼梯问题 ####

题目：假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

*  注意：给定 *n* 是一个正整数。

我们就一起来分析一下：

首先要定义一个一维数组来记录不同楼层的状态。

1.  确定dp数组以及下标的含义dp\[i\]：爬到第i层楼梯，有dp\[i\]种方法。
2.  从dp\[i\]的定义可以看出，dp\[i\] 可以有两个方向推出来。首先是dp\[i - 1\]，上i-1层楼梯，有dp\[i - 1\]种方法，那么再一步跳一个台阶不就是dp\[i\]了么。还有就是dp\[i - 2\]，上i-2层楼梯，有dp\[i - 2\]种方法，那么再一步跳两个台阶不就是dp\[i\]了么。那么dp\[i\]就是 dp\[i - 1\]与dp\[i - 2\]之和！所以就得出dp\[i\] = dp\[i - 1\] + dp\[i - 2\] 。
3.  再回顾一下dp\[i\]的定义：爬到第i层楼梯，有dp\[i\]中方法。所有对于dp\[0\]来说，我个人认为跑到第0层，方法就是0啊，一步只能走一个台阶或者两个台阶，然而楼层是0，直接站楼顶上了，就是不用方法，dp\[0\]就应该是0，从dp数组定义的⻆度上来说，dp\[0\] = 0 也能说得通。需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。所以本题其实就不应该讨论dp\[0\]的初始化！童鞋们都知道dp\[1\] = 1，dp\[2\] = 2。所有其实可以不考虑dp\[0\]。如果要初始化，只初始化dp\[1\] = 1，dp\[2\] = 2，然后从i = 3开始递推，这样符合dp\[i\]的定义。
4.  确定遍历顺序从递推公式dp\[i\] = dp\[i - 1\] + dp\[i - 2\];中可以看出，遍历顺序一定是从前向后遍历的。
5.  dp数组举例:当n=5，dp\[n\]=8，看看究竟是不是和自己推导的一样。此时细心的小伙伴应该发现了，这就是斐波那契数列啊。唯一的区别是，没有讨论dp\[0\]应该是什么，因为dp\[0\]在本题没有意义！

C++代码如下：

#include<iostream>
    #include<vector>
    using namespace std;
    int main()
    {
        
        int n;
        cin>>n;
        vector<int>dp(n+1);
        if(n==0)cout<<"0";
        else if(n==1)cout<<"1";
        else if(n==2)cout<<"2";
        else
        {
        
            dp[0]=0;
            dp[1]=1;
            dp[2]=2;
            for(int i=3; i<=n; i++)
            {
        
                dp[i]=dp[i-1]+dp[i-2];
            }
            cout<<dp[n];
        }
    }

时间复杂度：O(n)，空间复杂度：O(n)。

运行结果：  
![在这里插入图片描述][498258c9155742da990b4ce2f40fbe6f.png_pic_center]

### 感想： ###

真的，对于斐波那契数列问题，第一次做感觉很easy，但第一次拿到爬楼梯问题时，可能真的不知所措，再深入了解了动态规划之后，这爬楼梯问题也就迎刃而解了。

动态规划的大致思想大概都是这样的，自己去多摸索，多做题吧。其实重点可能还是数学思维，这个真的很重要！

如有要改善的地方，请及时指出。若遇到更妙的动态规划的题目，我将会进行更新！

[Link 1]: https://blog.csdn.net/youngyangyang04/category_9780972.html
[0d36f68b29c347229ffb46a2bd975812.png_pic_center]: https://img-blog.csdnimg.cn/0d36f68b29c347229ffb46a2bd975812.png#pic_center
[498258c9155742da990b4ce2f40fbe6f.png_pic_center]: https://img-blog.csdnimg.cn/498258c9155742da990b4ce2f40fbe6f.png#pic_center