动态规划 爬楼梯 递推公式分析

首先看题目

 在代码随想录中是这么描述的

 我第一次看的时候很不理解，dp[i - 1]再跳一步一个台阶就是dp[i]，dp[i - 2]再跳一步两个台阶就是dp[i]，那递推公式不是应该是dp[i] = dp[i - 1] + 1 + dp[i - 2] + 1吗，因为dp[i - 1]和dp[i - 2]都需要再来一个步骤才能得到dp[i]。

但是但是，题目问的是，需要多少种方法达到i，而不是需要多少个步骤达到i，dp[i]中存放的，是到达i阶的方法个数

题目中描述，要么走一个台阶，要么走两个台阶。i 与 i - 1 只差一个台阶，i 与 i - 2 只差两个台阶，而dp[i - 1]代表的是到达 i - 1阶的方法个数，那么只需要在dp[i - 1]的方法后再走一个台阶即可， dp[i - 2] 代表的是到达 i - 2 阶的方法个数，只需要在dp[i - 2]方法后再走两个台阶即可。

可以得出 dp[i] = 到达第i - 1阶的方法中再走一个台阶 + 到达第i - 2阶的方法中再走两个台阶

我的文字描述可能还是让人不太清楚，那我们画图来举例

到达第一阶有一种方法，就是走一个台阶，图中为 1

到达第二阶有两种方法，1. 走一个台阶，再走一个台阶，图中为 1 + 1

                                        2. 走两个台阶，图中为 2

根据公式，到达第三阶的方法，就是在到达第二阶的方法中再走一个台阶 + 到达第一阶的方法中再走两个台阶

        到达第二阶的方法为 1 + 1 和 2，那么到达第二阶的方法再走一个台阶，方法为 1 + 1 + 1 和 2 + 1

        到达第一阶的方法为1，那么到达第一阶的方法再走两个台阶，方法为 1 + 2

        所以到达第三阶的方法有3种，分别为 1 + 1 + 1，2 + 1，1 + 2

让我们继续举例

根据公式，到达第四阶的方法，就是到达第三阶的方法中再走一个台阶 + 到达第二阶的方法中再走两个台阶

        到达第三阶的方法为 1 + 1 + 1，2 + 1，1 + 2，再走一个台阶，则方法为1 + 1 + 1 + 1，

        2 + 1 + 1,1 + 2 + 1

        到达第二阶的方法为1 + 1，2，再走两个台阶，则方法为1 + 1 + 2，2 + 2

        所以最终到达第四阶的方法总共有5种，为1 + 1 + 1 + 1，2 + 1 + 1，1 + 2 + 1，1 + 1 + 2，

        2 + 2

其余台阶都是这么推出来的

所以才能得出dp[i] = dp[i - 1] + dp[i - 2]

灵感来源于力扣评论区：