每日leetcode[爬楼梯]

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

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

解题思路：

每次爬楼梯的方案数入来一一列举出来会很麻烦，而且容易错误，不难发现，此层的阶数方案和上一层以及上上一层有关系，因为最后一次的爬楼梯阶数可能是一层也可能是两层，所以

f(x)=f(x-1)+f(x-2);

由转移方程得到结果，所以我们只需要算出前两次的方案数，后面逐步进行累加即可；

f(0)=0,f(1)=1;

怎么实现呢，寻找规律，我们可以发现这其实是滚动数组的体现；//这里是解题关键

三个变量

p q t

t=p+q;p,q一直在向前移动

class Solution {

public:

    int climbStairs(int n) {

      int p=0;

      int q=0;

      int t=1;

      for(int i=1;i<=n;i++)//注意这里的范围

      {

          p=q;

          q=t;

          t=p+q;

      }

  return  t;

    }

};