下面通过表格来解释 f(n)自底向上的求解过程。
台阶数 1 2 3 4 5 6 7 8 9走法数 1 2
表格的第一行代表了楼梯台阶的数目，第二行代表了若干台阶对应的走法数。
其中f(1) = 1 和 f(2) = 2是前面明确的结果。
第一次迭代，如果台阶数为 3 ，那么走法数为 3 ，通过 f(3) = f(2) + f(1)得来。
台阶数 1 2 3 4 5 6 7 8 9走法数 1 2 3
第二次迭代，如果台阶数为 4 ，那么走法数为 5 ，通过 f(4) = f(3) + f(2)得来。
台阶数 1 2 3 4 5 6 7 8 9走法数 1 2 3 5
由此可见，每一次迭代过程中，只需要保留之前的两个状态，就可以推到出新的状态。
show me the code
1int f(int n) {2 if (n == 1) return 1;
3 if (n == 2) return 2;
4 // a 保存倒数第二个子状态数据，b 保存倒数第一个子状态数据， temp 保存当前状态的数据
5 int a = 1, b = 2;
6 int temp = a + b;
7 for (int i = 3; i <= n; i++) {
8 temp = a + b;
9 a = b;
10 b = temp;
11 }
12 return temp;
13}
程序从 i = 3 开始迭代，一直到 i = n 结束。每一次迭代，都会计算出多一级台阶的走法数量。迭代过程中只需保留两个临时变量 a 和 b ，分别代表了上一次和上上次迭代的结果。为了便于理解，引入了temp变量。temp代表了当前迭代的结果值。
看一看出，事实上并没有增加太多的代码，只是简单的进行了优化，时间复杂度便就降为O(n)，而空间复杂度也变为O(1)，这，就是「动态规划」的强大！
详解动态规划「动态规划」中包含三个重要的概念：
【最优子结构】
【边界】
【状态转移公式】
在「 爬台阶问题 」中
f(10) = f(9) + f(8) 是【最优子结构】
f(1) 与 f(2) 是【边界】
f(n) = f(n-1) + f(n-2) 【状态转移公式】
「 爬台阶问题 」 只是动态规划中相对简单的问题，因为它只有一个变化维度，如果涉及多个维度的话，那么问题就变得复杂多了。
难点就在于找出 「动态规划」中的这三个概念。
比如「 国王和金矿问题 」。
国王和金矿问题有一个国家发现了 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
找出 「动态规划」中的这三个概念
国王和金矿问题中的【最优子结构】国王和金矿问题中的【最优子结构】有两个：
① 4 金矿 10 工人的最优选择
② 4 金矿 （10 - 5） 工人的最优选择
4 金矿的最优选择与 5 金矿的最优选择之间的关系是
MAX[（4 金矿 10 工人的挖金数量），（4 金矿 5 工人的挖金数量 + 第 5 座金矿的挖金数量）]
国王和金矿问题中的【边界】国王和金矿问题中的【边界】 有两个：
① 当只有 1 座金矿时，只能挖这座唯一的金矿，得到的黄金数量为该金矿的数量
② 当给定的工人数量不够挖 1 座金矿时，获取的黄金数量为 0
国王和金矿问题中的【状态转移公式】我们把金矿数量设为 N，工人数设为 W，金矿的黄金量设为数组G[]，金矿的用工量设为数组P[]，得到【状态转移公式】：
边界值：F(n,w) = 0 (n <= 1, w < p[0])
F(n,w) = g[0] (n==1, w >= p[0])
F(n,w) = F(n-1,w) (n > 1, w < p[n-1])
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1]) + g[n-1]) (n > 1, w >= p[n-1])
国王和金矿问题中的【实现】先通过几幅动画来理解 「工人」 与 「金矿」 搭配的方式
1.只挖第一座金矿