力扣70:爬楼梯

题目

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

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

思路

首先我们先列出来前几个台阶的答案从第一个开始：1，2，3，5。前几个台阶我们比较好想所以可以直接算出来，我们发现这里面是不是有什么规律啊，第三个台阶的答案是一二台阶的和，第四个台阶的答案是二三台阶的和。这是巧合还是规律呢？我们可以再写后面两个的答案或者仔细观察一下题目。
这就是规律不是巧合，为什么呢？题目说了我们每次只能爬一个或两个台阶那么我们想要爬到第四个台阶是不是只能从第二个一下走两个台阶到或者从第三个一下走一个台阶到。所以呢想要到第四个台阶我们必须先到第二个或者第三个台阶，他们俩有各有多少种走法相加不就是第四个台阶的走法吗？所以从第三个台阶开始每层台阶的答案就是前两层台阶的答案相加，我们假设f(n)是第n层台阶的走法，那么f(n) = f(n-2) + f(n-1)。
那么有了这个方程我们不就可以最底层开始一步一步的算到第n层吗，不就得到答案了吗？这道题用到的思想是动态规划，我们可以发现我们每层得到的数都是这层的最终答案也就是把题目从得到第n层方法转换为了得到第n-2，第n-1层台阶的答案以此类推最终到第0层。所以既然能从上往下推也就可以从下往上得到答案，这就是动态规划的思想也就是把一个问题拆成子问题然后通过得到子问题的答案来推得原来问题的答案。而上面那个方程就是转换方程。

代码

class Solution {
public:int climbStairs(int n) {// 先得出爬一楼和二楼的值int p = 1;int q = 2;if (n == 1) {return p;} else if (n == 2) {return q;} else {// 从三楼开始// 因为我们一次只能爬一楼或者二楼// 所以从第三层开始每层的方法就等于// 前两楼的方法的总和int r = 0;for (int i = 3; i <= n; i++) {r = p + q;p = q;q = r;}return r;}}
};