题目地址(70. 爬楼梯)

https://leetcode-cn.com/problems/climbing-stairs/

题目描述

  1. 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
  3. 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
  5. 注意：给定 n 是一个正整数。
  7. 示例 1：
  9. 输入： 2
  10. 输出： 2
  11. 解释： 有两种方法可以爬到楼顶。
  12. 1.  1 阶 + 1 阶
  13. 2.  2 阶
  15. 示例 2：
  17. 输入： 3
  18. 输出： 3
  19. 解释： 有三种方法可以爬到楼顶。
  20. 1.  1 阶 + 1 阶 + 1 阶
  21. 2.  1 阶 + 2 阶
  22. 3.  2 阶 + 1 阶

前置知识


公司

  • 暂无

思路

image.png
也就是当前的方法数等于 -1的方法数加上-2 的方法数 这样一看和斐波那契数列是一样的 只是具体到了解决方法
台阶数为0的时候就不考虑了 因为题目中的说为正整数

完全背包

bag = n 物品 = [1,2]

  1. dp[i]表示有多少种方法能从0-> i
  2. dp[i] += dp[i-j] 因为是求到xxx有多少种方法
  3. 初始化 dp[0] =1 问填满背包的方法
  4. 完全背包 求排列 背包在外 物品在内 正序

    关键点


代码

  • 语言支持：Java

Java Code:


class Solution {
        public int climbStairs(int n) {
            //因为下面对2操作了 所以对<2的数据处理 不然就角标越界了
            if(n<=1){
                return 1;
            }
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n ; i++) {
                dp[i] = dp[i-1] +dp[i-2];
            }
            return dp[n];
        }
    }
  • 完全背包法
    class Solution {
      public int climbStairs(int n) {
          int[] dp = new int[n + 1];
          dp[0] = 1;
          dp[1] = 1;
          for (int i = 2; i <=n ; i++) {
              for (int j = 1; j <= 2; j++) {
                  dp[i] += dp[i - j];
              }
          }
          return dp[n];
      }
  }
    复杂度分析

令 n 为数组长度。

  • 时间复杂度：70. 爬楼梯 3 - 图2#card=math&code=O%28n%29&id=Ow8zW)
  • 空间复杂度：70. 爬楼梯 3 - 图3#card=math&code=O%28n%29&id=mQXUH)