做题过程中第一时间想到的是使用递归思想,在提交代码后,发现在数据较大的时候,会出现数据溢出。
class Solution {public int climbStairs(int n) {if (n<=1){return 1;}if (n<3){return n;}return climbStairs(n-1) + climbStairs(n-2);}}
之后采用滚动数组来实现了代码,如图所示
实现代码如下
class Solution {public int climbStairs(int n) {int p=0,q=0,r=1;for(int i=1;i<=n;++i){p=q;q=r;r=p+q;}return r;}}
力扣:爬楼梯(假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?)