LeetCode（初级算法）动态规划篇---爬楼梯

末蓝、 2022-05-25 13:44 229阅读 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 步

## 解析 ##

### 方法一 ###

可以把他转换成递归公式：a\[i\]= a\[i-1\]+a\[i-2\]

也可以把他抽象地理解成一个二叉树，计算它的叶子节点个数，在满足条件的时候进行计数

#### 代码 ####

public int climbStairs(int n) {
           if(n<0)return 0;  //这是那些不正确的结果
           else if(n==0)return 1;    //这是正确的结果
           return climbStairs(n-1)+climbStairs(n-2);
       }

#### 拓展 ####

public int climbStairs(int n) {
           if(n<0)return 0;  
           else if(n==0)return 1;    
           return climbStairs(n-3)+climbStairs(n-5);   //爬3个台阶或者是5个台阶的组合
       }

**优点：**

它不仅仅适用于每次爬1与2个台阶的问题，也适用于爬多个台阶的问题

**缺点：**

速度慢，不仅仅只是因为递归，还有因为它还要排除不正确的组合方式 (1和2的组合不需要)

！！！在LeetCode中这种方法会超出时间限制，但是可以解出答案的

### 方法二 ###

输入数(N)  1   2   3   4   5   6    7      8
    
    组合数(a)  1   2   3   5   8   13   21     34

可见刚好呈现 a\[N\]= a\[N-1\]+a\[N-2\] （N>2）

#### 代码 ####

public int climbStairs2(int n) {
           int a=1,b=2,c=0;
           if(n==1)return a;
           else if(n==2)return b;
    
           for(int i =2;i<n;i++) {
               c = a+b;
               a = b;
               b = c;
           }
           return c;  
       }

**优点**：速度快

**缺点**：只适用于步数1与2组合的情况