什么是动态规划？

动态规划算法通过将原问题分解为多个子问题，然后得到这些子问题的最优解，最后通过组合这些子问题的最优解得到原问题的最优解。

我们以计算斐波拉契数为例，来看看最简单的动态规划是怎么工作的。斐波拉契数是一组特殊的序列，序列的前两个数是0和1，从序列的第三个数开始，它的值等于前两个数的和。比如 0, 1, 1, 2, 3, 5, 8, ...，如果用代码来表示

很明显可以看出，为了计算第 n 个斐波拉契数值，我们可以先计算第n-1和第n-2个数值，然后将它们相加就得到了第n个数值。

同样的为了计算第n-1个数值，我们需要计算第n-2和第n-3个数值，这里我们发现，第n-2个数值已经在计算第n个数值时计算过了，这就是动态规划最重要的两个性质之一重叠子问题，比如说计算fib(4)时，我们可以看到fib(2)、fib(1)都被计算了多次。

动态规划还有一个性质是最优子结构，也就是说原问题的最优解能从子问题的最优解中推导出来，在动态规划中一般用一个状态转移方程来表示，在斐波拉契问题中是

下面是最简单使用递归来求解斐波拉契序列的实现，由于子问题重叠，导致子问题被多次计算，效率低下。

下面看看使用动态规划算法来求解斐波拉契序列。

一、自顶向下——记忆化递归

由于子问题的解可能多次使用，所以我们将所有子问题的解缓存下来，当再次使用无需再次计算，而是从缓存中取值，这种方式叫做记忆化。

二、自底向上——制表

这种方式使用迭代来替换递归，从最小的问题开始计算，然后将子问题解填入到表中，然后通过这些子问题解一步步计算更大的问题的解，最后得到原问题的解，这个过程就像是在制作一个子问题解的表格，下面看看使用制表的方式计算斐波拉契序列的具体实现。

爬楼梯

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

示例 1：

输入： 2
输出： 2

解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入： 3
输出： 3

解释： 有三种方法可以爬到楼顶。

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

这个题目其实和求斐波拉契序列是一个类型。如果我们不将问题拆分成小问题，这看上去就很难解决，由于一次可以爬1阶或者2阶，要爬到n阶，那就是相对于1阶和2阶的各种排列组合。如果换个思维来考虑，要爬到n阶，那么之前的一步，要么是在第n-1阶，要么是在第n-2阶，所以爬到第n阶最后一步有两种方式

1. 第一种是到是n-1阶，再爬1阶。
2. 第二种是到第n-2阶，再爬2阶。

所以我们只要知道有多少种方式爬到第n-1阶和第n-2阶，我们就能知道有多少种方式爬到第n阶了，状态转移方程如下