求最值问题，比如最长序列、最短距离等，不考虑时间和空间都可以通过暴力穷举的方式遍历获得结果，通过对穷举的过程进行优化减少重复开销的过程，即动态规划。
动态规划的重点，就是如何确定 状态转移方程 和 通过 备忘录 空间换时间降低时间复杂度（优化穷举）。
以拿硬币举例，从 1,2,5 从拿硬币，求 amount 满足 11 时的最少硬币数量。
状态转移方程构建
1.确定 base case
即确定满足什么边界条件时 return 直接结束当前递归。
其中，例子的边界条件为：当 amount == 0 时 返回 0，当 amount < 0 时无解，返回 -1。
2.确定 状态
即原问题和子问题都会变化的变量。
其中，例子的状态为 amount，可以看出每拿走一个硬币 amount 就会改变，并向 base case 靠近，直至匹配。
3.明确 选择
即导致状态改变的行为。
其中，例子的选择为拿硬币。
4.明确 dp 的定义
dp 函数即递归找最值的函数，递归一般分为 自顶向下 和 自底向上 两种，框架如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| # 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
for 选择 in 所有可能的选择:
# 此时的状态已经因为做了选择而改变
result = 求最值(result, dp(状态1, 状态2, ...))
return result
# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
|
对比如下解法看出区别：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
int fib(int N) {
int[] memo = new int[N + 1];
return dp(memo, N);
}
int dp(int[] memo, int n) {
if (n == 0 || n == 1) return n;
if (memo[n] != 0) return memo[n];
memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
return memo[n];
}
int fib(int N) {
if (N == 0) return 0;
int[] dp = new int[N + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
|
备忘录 memo
备忘录的作用，用于解决重复计算的问题。每次解决子问题的时候，先去备忘录查一下是否有结果，如果有直接使用，避免重复计算。例子如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int fib(int N) {
int[] memo = new int[N + 1];
return dp(memo, N);
}
int dp(int[] memo, int n) {
if (n == 0 || n == 1) return n;
if (memo[n] != 0) return memo[n];
memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
return memo[n];
}
|
