Leetcode 题目解析：70. 爬楼梯

系列文章：

算法题目解析：从一道题目看动态规划

Leetcode 题目解析：274. H 指数

Leetcode 题目解析：279. 完全平方数

Leetcode 题目解析：287. 寻找重复数

Leetcode 题目解析：211. 添加与搜索单词 - 数据结构设计

一 摘要

在前面算法题目解析：从一道题目看动态规划这篇文章中，描述了动态规划的概念、原理和典型示例，今天用几道典型的动态规划题目来做为练手，达到掌握的目的。70. 爬楼梯是一道简单题，但比较典型，先从它开始。

二 题目描述与示例

2.1 描述

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

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

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

2.2 示例

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

三 解析

3.1 题目解析

题目比较清晰，要爬n阶楼梯，每次可选向上1/2个台阶，计算所有可能。如果我们从最后一次的选择倒推，f(n)表示到达第n个台阶的可能方法数，那么就可以很容易得到f(n) = f(n-1)+f(n-2)。

3.2 解法思路

3.2.1 动态规划

我们先再回顾一下动态规划算法：动态规划算法通常基于一个递推公式（状态转移方程）和一个或多个初始状态。当前子问题的解将由上一次子问题的解推导而出。很显然，题目符合这个特征。因此可以使用动态规划的方法。

3.2.2 准备条件

在使用动态规划算法解题时，需要我们给出两个内容：（1）状态转移方程，（2）明确边界条件。

（1）比较容易，f(n) = f(n-1)+f(n-2)就是我们这个场景的状态转移方程；

（2）边界条件，因为状态转移方程需要先知道f(n-1)和f(n-2)，所以说递推的计算只能从f(2)开始，并初始化f(0)和f(1)的值。f(0)和f(1)就是这道题目的边界。我们是从0阶开始向上爬，爬到第0层，可以看做只有一种方法；从第0阶到第1阶也只有一种方法（即只爬1个台阶），故f(1)=1。

3.2.3 实现方法

有了状态转移方程和边界条件，我们就可以向下推最终结果。比较容易想到的是，从2到n执行遍历，逐个计算f(i)并存储结果，直到计算到f(n)为止。一次遍历，存储n个中间和最终结果，所以时间复杂度和空间复杂度都是O(n)。

时间复杂度在当前方法下不太容易优化，但空间是否可行呢？因为每次计算时，f(i)只依赖前面两个值，所以如果我们采用滚动数组的方式，就可以把空间复杂度降低到O(1)。如果滚动数组不好理解，也可以简单地定义n_1 和 n_2两个变量，每计算一次后，更新n_1=f(i)，n_2=f(i-1)，下次就可以用这两个值计算f(i+1)了。

3.3 代码实现

public int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q; 
        q = r; 
        r = p + q;
    }
    return r;
}