斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。
示例 1：
- 输入：2
- 输出：1
- 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
- 输入：3
- 输出：2
- 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
- 输入：4
- 输出：3
- 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
- 0 <= n <= 30
思路
本来这题应该是用递归写的，但作为DP的入门题也合适
先说明一下，DP五部曲:
- 确定DP数组以及数组的下标定义
- 确定递推公式
- 确定DP数组如何初始化
- 确定遍历顺序
- 打印DP数组（主要用于debug）
五部曲分析
那下面就用这题来做一个示范
1、确定DP数组以及数组的下标定义
做动规题都需要先明确dp数组dp[i]的定义
在本题中，dp[i]应该指的是：第i个斐波那契数的数值是dp[i]
2、确定递推公式
因为刚刚入门，就目前我的理解，所谓的递推公式就是题目中的某种解决问题的思路的抽象形式
像这里，题目直接就给了F(n) = F(n - 1) + F(n - 2)
这个公式就是用来求斐波那契数的，那么这个公式也就是要找的递推公式（直接给出了所以本题简单）
结合本题dp[i]的定义可以得到最终需要的递推公式：dp[i] = dp[i - 1] + dp[i - 2]
3、确定DP数组初始化方式
题目也给了：F(0) = 0，F(1) = 1，所以初始化方式如下：
dp[0] = 0;
dp[1] = 1;
4、确定遍历顺序
因为dp[i] = dp[i - 1] + dp[i - 2]，先有的dp[i - 1]和dp[i - 2]才能求dp[i]
故遍历顺序应该是从前向后
5、打印DP数组
这一步的意思就是，根据我们推断的递推公式，将dp[i]的值自行计算出来看看对不对
代码
class Solution {
public:
int fib(int n) {
if(n <= 1) return n;//如果n小于等于1，即直接得到第1个斐波那契数（0 + 1），因此直接返回n即可。
vector<int> dp(n + 1);//创建dp数组
dp[0] = 0;//初始化dp数组
dp[1] = 1;
for(int i = 2; i <= n; ++i){//遍历
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];//返回dp数组中n处的值，即第n个斐波那契数
}
};
爬梯子
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
- 输入： 2
- 输出： 2
- 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
- 输入： 3
- 输出： 3
- 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
思路
先看看题目描述，要求的是爬到楼顶有多少种方法
再看一下示例2，
爬到第一层楼梯有1种方法；
爬到第二层楼梯有2种方法；（一阶一阶爬、一次爬两阶）
那么爬到第三层楼梯就有3种方法；（一阶一阶爬、一阶+二阶、二阶+一阶）
实际上到第三层楼梯的方法数可以通过到第一层和到第二层的方法数推出
那么就可以用dp
五部曲
还是五步走
1、确定dp数组的含义
dp[i]:爬到第i层楼梯有dp[i]种方法
2、确定递推公式
如何推出递推公式？要结合对于dp[i]的定义
1阶 1种 dp[i-2],上i-2层楼梯，有dp[i - 2]种方法(现在是i-2阶，再往上走1阶到i-1阶)
2阶 2种 dp[i-1],上i-1层楼梯，有dp[i - 1]种方法(现在是i-1阶，再往上走1阶到i阶)
3阶 3种 dp[i],上i层楼梯，有dp[i]种方法
好，到第i层楼梯（也就是第3层），按dp数组定义来是有dp[i]种方法
现在往回看，在i-2层时，我们可以选择一次爬两阶，然后上到第i层；同理在i-1层时，我们也可以选择一次爬一阶，然后上到第i层；
这说明，到达第i层楼梯的dp[i]种方法中包含着爬上i-2层和i-1层时的方法
由此可以总结出到达第i层楼梯的递推公式：dp[i] = dp[i - 2] + dp[i - 1]
3、确定dp数组的初始化方式
之前在 斐波那契数 中，我们讨论初始化时，是有对dp[0]进行初始化的
但是这里可以不用讨论dp[0]，下面来说具体原因
在确定dp数组的初始化方式时，我们仍然要遵循第一步中给dp数组下的定义，即dp[i]:爬到第i层楼梯有dp[i]种方法
根据此定义来解释dp[0]就有点问题，爬到第0层楼有dp[0]种方法？
都0层楼了，相当于不用走直接在终点了，这样就可能会有多种解释
最好的办法就是不讨论dp[0]的情况，而且题目中说了n是一个正整数，根本就没说n有为0的情况。
那么根据dp数组的定义，我们可以得到以下初始化：
dp[1] = 1；
dp[2] = 2；
显然这是无争议，也是符合dp数组定义的
4、确定遍历顺序
分析到这里了，你肯定发现这题和斐波那契数其实是一样的
第i个数（阶梯）需要依靠第i-1和i-2个数（阶梯）确定
自然的，本题的遍历顺序也需要是从前向后的
代码
因为我们不讨论dp[0]，所以应该从dp[3]开始累加
步骤：
1、处理n小于等于1的情况
2、创建dp数组，并初始化
3、按照设定的顺序开始遍历累加dp数组，最后返回dp[n]
class Solution {
public:
int climbStairs(int n) {
if(n <= 1) return n;//如果n小于等于1，那么只有一种爬楼梯的方法，即直接到达目标楼层，因此直接返回n即可。
vector<int> dp(n + 1);//创建dp数组
dp[1] = 1;//初始化dp数组
dp[2] = 2;
for(int i = 3; i <= n; ++i){// 注意i是从3开始的
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];//返回dp数组中n处的值，即爬到第i层楼梯有dp[i]种方法
}
};
在这段代码中，如果n小于等于1，那么只有一种爬楼梯的方法，即直接到达目标楼层，因此直接返回n即可。
如果n大于1，那么创建一个大小为n+1的dp数组来记录每个楼梯台阶的爬楼梯方法数。然后初始化dp数组的前两个元素为1和2，因为到达第一层楼梯只有一种方法，到达第二层楼梯有两种方法。接着通过循环，从第三个元素开始依次计算每个楼梯的爬楼梯方法数，即dp[i] = dp[i - 2] + dp[i - 1]，最后返回dp数组中n处的值，即到达第n层楼梯的爬楼梯方法数。