什么是动态规划？
学习数据结构与算法
动态规划算法通过将原问题分解为多个子问题，然后得到这些子问题的最优解，最后通过组合这些子问题的最优解得到原问题的最优解。
我们以计算斐波拉契数为例，来看看最简单的动态规划是怎么工作的。斐波拉契数是一组特殊的序列，序列的前两个数是0和1，从序列的第三个数开始，它的值等于前两个数的和。比如 0, 1, 1, 2, 3, 5, 8, ...，如果用代码来表示
Fib(n) = Fib(n-1) + Fib(n-2), 当 n > 1 时很明显可以看出，为了计算第 n 个斐波拉契数值，我们可以先计算第n-1和第n-2个数值，然后将它们相加就得到了第n个数值。
同样的为了计算第n-1个数值，我们需要计算第n-2和第n-3个数值，这里我们发现，第n-2个数值已经在计算第n个数值时计算过了，这就是动态规划最重要的两个性质之一重叠子问题，比如说计算fib(4)时，我们可以看到fib(2)、fib(1)都被计算了多次。
动态规划还有一个性质是最优子结构，也就是说原问题的最优解能从子问题的最优解中推导出来，在动态规划中一般用一个状态转移方程来表示，在斐波拉契问题中是
Fib(n) = Fib(n-1) + Fib(n-2), 当 n > 1 时下面是最简单使用递归来求解斐波拉契序列的实现，由于子问题重叠，导致子问题被多次计算，效率低下。
1public class Main {
2
3 public static void main(String[] args) {
4 System.out.println(fib(20));
5 }
6
7 public static int fib(int n) {
8 if (n < 2)
9 return n;
10 return fib(n - 1) + fib(n - 2);
11 }
12}下面看看使用动态规划算法来求解斐波拉契序列。
一、自顶向下——记忆化递归
由于子问题的解可能多次使用，所以我们将所有子问题的解缓存下来，当再次使用无需再次计算，而是从缓存中取值，这种方式叫做记忆化。
1import java.util.HashMap;
2import java.util.Map;
3
4public class Main {
5
6 private static final Map<Integer, Integer> cached = new HashMap<>();
7
8 public static void main(String[] args) {
9 System.out.println(fib(20));
10 }
11
12 public static int fib(int n) {
13 if (n < 2)
14 return n;
15 if (!cached.containsKey(n)) {
16 int value = fib(n - 1) + fib(n - 2);
17 cached.put(n, value);
18 return value;
19 }
20 return cached.get(n);
21 }
22}
23二、自底向上——制表
这种方式使用迭代来替换递归，从最小的问题开始计算，然后将子问题解填入到表中，然后通过这些子问题解一步步计算更大的问题的解，最后得到原问题的解，这个过程就像是在制作一个子问题解的表格，下面看看使用制表的方式计算斐波拉契序列的具体实现。
1public class Main {
2
3 public static void main(String[] args) {
4 System.out.println(fib(20));
5 }
6
7 public static int fib(int n) {
8 if (n <= 0) {
9 return 0;
10 }
11 int[] dp = new int[n + 1];
12 dp[0] = 0;
13 dp[1] = 1;
14 for (int i = 2; i < dp.length; i++) {
15 dp[i] = dp[i - 1] + dp[i - 2];
16 }
17 return dp[dp.length - 1];
18 }
19}
20爬楼梯
假设你正在爬楼梯，需要 n 阶你才能到达楼顶，每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
这个题目其实和求斐波拉契序列是一个类型。如果我们不将问题拆分成小问题，这看上去就很难解决，由于一次可以爬1阶或者2阶，要爬到n阶，那就是相对于1阶和2阶的各种排列组合。如果换个思维来考虑，要爬到n阶，那么之前的一步，要么是在第n-1阶，要么是在第n-2阶，所以爬到第n阶最后一步有两种方式
- 第一种是到是n-1阶，再爬1阶。
- 第二种是到第n-2阶，再爬2阶。
所以我们只要知道有多少种方式爬到第n-1阶和第n-2阶，我们就能知道有多少种方式爬到第n阶了，状态转移方程如下
f(n) = f(n-1) + f(n-2)有人可能会想从第n-2阶爬1阶再爬1阶也不可以吗？从第n-2阶爬1阶就到第n-1阶了，实质上这就算是第一种情况了。
1class Main {
2
3 public static void main(String[] args) {
4 System.out.println(climbStairs(3));
5 }
6
7 public static int climbStairs(int n) {
8 if (n == 1) {
9 return 1;
10 }
11 int[] dp = new int[n + 1];
12 dp[1] = 1;
13 dp[2] = 2;
14 for (int i = 3; i <= n; i++) {
15 dp[i] = dp[i - 1] + dp[i - 2];
16 }
17 return dp[n];
18 }
19}