70.爬楼梯

发表于： 分类于：
字数： 787 阅读：≈ 2分钟

😄70.爬楼梯

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

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

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

示例 ：

  • 输入： 2
  • 输出： 2
  • 解释： 有两种方法可以爬到楼顶。
    • 1 阶 + 1 阶
    • 2 阶

思路

基本思想

简单思想

以某一个阶梯n为例，走到这个阶梯的方式有两种，从n-1走一步或者从n-2走两步，这是两种方案，所以需要将这两种方案相加

而到达n-1和n-2的方案也是如此推出，所以可以得到，f(n)=f(n-1)+f(n-2)，从前面的状态推导出后面的状态，我们采用从前向后推导的方式计算出f(n)的值即可

背包问题

可以将阶梯数看作是背包的容量，然后一次走一步或者两步最终到达阶梯n可以看做使用1和2填充背包，最终恰好将背包填充满，求所有的方案数，这个方案数是排列的方案数，因为[1,2]和[2,1]不一样

执行流程

简单思想

从前向后遍历，由于n是一个正整数不为0，所以初始值有两个，res[1]=1,res[2]=2，从第三级阶梯开始统计，之后res[n]的值由res[n-1]和res[n-2]共同推导得到，最后返回res[n]的值就是最终结果

背包问题

和其他背包问题一样，只不过此时物品只有两个，1和2

代码

根据以上分析，得出以下代码：

简单思想 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        int left=1;
        int right=2;
        for(int i=3;i<=n;++i){
            int sum=right+left;
            left=right;
            right=sum;
        }
        return right;
    }
};

背包问题 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int climbStairs(int n) {
        //使用另一种思想
        //背包容量为n，使用1和2填充背包，背包刚好填充满的方案数有多少
        //1,2的顺序随意
        vector<int> dp(n+1,0);
        vector<int>nums{1,2};
        dp[0]=1;
        for(int j=0;j<=n;++j){
            for(int i=0;i<nums.size();++i){
                if(j-nums[i]>=0){//当前物品可以装下
                    dp[j]+=dp[j-nums[i]];
                }
            }
        }
        return dp[n];
    }
};

总结

简单思想中，主要是到达n的方法由到达n-1和到达n-2的方法推出，即f(n)=f(n-1)+f(n-2)

转化为背包问题之后，变成了完全背包的排列问题，直接按照流程进行判断即可