题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

思路

动态规划的方法去解决：

1. 分析：

   爬1级台阶：1种方法（爬1级）
   爬2级台阶：2种方法（最后一次爬1级或2级：1+1，2）
   爬3级台阶：3种方法（最后一次爬1级或2级：1+1+1，2+1，1+2）
   爬4级台阶：5种方法（最后一次爬1级或2级：1+1+1+1，2+1+1，1+2+1，1+1+2,2+2）
   f(x)表示方案数：爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶：f(x) = f(x-1) + f(x-2)

代码

class Solution {
    public int climbStairs(int n) {
        //r为最终返回的结果
        int p = 0, q = 0, r = 1;
        for(int i=1; i<=n; i++){
            //滚动数组
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

代码说明

注释见。。。