70. 爬楼梯

作者: 凌霄文强 | 来源:发表于2019-03-02 09:38 被阅读0次

题目描述

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

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

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶
    示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶
知识点

动态规划


Qiang的思路

经典的动态规划,当前位置的可能方案可能是从上一个台阶过来的,或者是从上上个台阶过来的,所以有公式:
S(n)=S(n-1)+S(n-2)

class Solution {
public:
    int climbStairs(int n) {
        int a=1,b=2;
        int res;
        if(n==1)
            res=a;
        else if(n==2)
            res=b;
        else
            for(int i=3;i<=n;i++){
                res=a+b;
                a=b;
                b=res;
            }
        return res;
    }
};

作者原创,如需转载及其他问题请邮箱联系:lwqiang_chn@163.com
个人网站:https://www.myqiang.top

相关文章

网友评论

    本文标题:70. 爬楼梯

    本文链接:https://www.haomeiwen.com/subject/llteuqtx.html