家庭网做网站php网站开发机试题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1. 递归（超时）

class Solution {
public:int climbStairs(int n) {if(n==1){return 1;}if(n==2){return 2;}return climbStairs(n-1)+climbStairs(n-2);}
};

2. 迭代（需要开大小为n+1的数组）

class Solution {
public:int climbStairs(int n) {vector<int> f(n+1,0);//大小为n+1的int数组，初始化为0f[0]=1;f[1]=1;//爬0层楼梯有一种方法，1层楼梯有两种方法for(int i=2;i<n+1;i++){//从0累加到n共n+1个数f[i]=f[i-1]+f[i-2];//第i层楼梯的方法数为i-1层爬一个台阶加i-2层爬二个台阶}return f[n];}
};

3. 滚动数组

 f[i]=f[i-1]+f[i-2]第 i 层状态只与第i-1层和i-2层有关，因此只需两个变量记录之前的状态即可。

class Solution {
public:int climbStairs(int n) {      int a=1,b=1;//a=f[i-2],b=f[i-1]int c;//c=f[i]for(int i=2;i<n+1;i++){//从0累加到n共n+1个数c=a+b;a=b;b=c;}return c;}
};