做网站怎么开后台,网站建设功能最全的软件,餐饮 公司 网站建设,嘉兴做微网站多少钱假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
1. 递归#xff08;超时#xff09;
class Solution {
public:int climbStairs(int n) {if(n1){return 1;}if(n2){return 2;}return climbStairs…假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
1. 递归超时
class Solution {
public:int climbStairs(int n) {if(n1){return 1;}if(n2){return 2;}return climbStairs(n-1)climbStairs(n-2);}
};
2. 迭代需要开大小为n1的数组
class Solution {
public:int climbStairs(int n) {vectorint f(n1,0);//大小为n1的int数组初始化为0f[0]1;f[1]1;//爬0层楼梯有一种方法1层楼梯有两种方法for(int i2;in1;i){//从0累加到n共n1个数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 a1,b1;//af[i-2],bf[i-1]int c;//cf[i]for(int i2;in1;i){//从0累加到n共n1个数cab;ab;bc;}return c;}
};
