你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【每日一题035】leetcode-70

2021-11-17 7:33:04

目录

  • 题目
  • 思路
  • 相关思考
  • 代码(C++/原创)

题目

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

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

思路

可以从题意得出,n格台阶的走法相当于n-1再走一个或者n-2再走两格,这就写出了一个比较简洁的递推式,利用递归的思想完成即可。

相关思考

直接递归调用在参数为45的时候超时了,解决办法是利用之前在背包问题中采用的办法,创建一个大小为3的int数组进行循环存储,每次计算都是直接将数组中的其他两个数字相加即可。

代码(C++/原创)

class Solution {
public:
    int a[3]={};
    int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        a[1]=1,a[2]=2;
        for(int i=3;i<=n;i++)
        {
            a[i%3]=a[(i-1)%3]+a[(i-2)%3];
        }
        return a[n%3];

    }
};