系列文章：

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

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;}