1. 介绍
动态规划的问题一般是求最值。比如求最长递增子序列、最小编辑距离等。
1.1 核心问题
求解动态规划问题的核心问题就是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。
1.2 三要素
重叠子问题、最优子结构、状态转移方程就是动态规划三要素。
1.2.1 重叠子问题
动态规划的穷举有点特别，因为这类问题存在“重叠子问题”，如果暴力穷举，效率会极其低下，所以需要“备忘录”或者“DP table”来优化穷举过程，避免不必要的计算。
1.2.2 最优子结构
动态规划问题一定会具备“最优子结构”，这样才能通过子问题的最值得到原问题的取值。
1.2.3 状态转移方程
穷举所有可行解其实并不是一件容易的事，只有列出正确的“状态转移方程”，才能正确的穷举。写出状态转移方程，这一步是最困难的。
1.3 写出正确的状态转移方程
想要写出正确的状态转移方程，一定要思考以下几点:
- 这个问题的base case(最简单情况)是什么?
- 这个问题有什么“状态”?
- 对于每个“状态”，可以做出什么“选择”使得“状态”发生改变？
- 如何定义dp数组/函数的含义来表现“状态”和“选择”？
1.4 框架
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2，...)
下面通过斐波那契数列和凑零钱这两个例子来讲解动态规划的基本原理。前者解释什么是重叠子问题，后者专注于如何列出状态转移方程。
2. 斐波那契数列
2.1 暴力递归
斐波那契数列的数学形式就是递归的，写成代码就是这样的:
int fib(int N) {
if(N == 0) return 0;
if(N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
但是该递归效率十分低下，低效在哪里？假设n=20，画出递归树:
注意:但凡遇到需要递归解决的问题，最好都画出递归树，这对分析算法的复杂度。寻找算法低效的原因都有巨大帮助。
这个递归树的意思是说，要想计算f(20)的值，就应该先计算出子问题f(19)和f(18)，然后计算f(19)，以此类推。最后当遇到f(1)或者f(2)的时候，结果已知。这样就能直接返回结果，递归树不再往下生长了。
2.2 重叠子问题
观察该递归树，可以很明显的看出有很多重复计算，比如f(18)被计算了两次，更何况还不止f(18)这一个节点被重复计算，所以这个算法极其低效。
这就是动态规划问题的第一个性质:重叠子问题。下面我们来解决这个问题。
2.3 带备忘录的递归解法
耗时的原因是计算，那么我们就可以造一个“备忘录”，每次计算出某个子问题的答案后别急着返回，先将其记到“备忘录”里再返回；每次遇到一个子问题先去“备忘录”里查一查，如果发现之前已经解决过这个问题，就直接把答案拿出来用，不要再耗时进行计算了。
一般使用一个数组充当“备忘录”，也可以是使用哈希表。
代码:
int fib(int N) {
if( N == 0 ) return 0;
// 将备忘录全初始化为0
vector<int> memo(N + 1, 0);
// 进行带备忘录的递归
return helper(memo, N);
}
int helper(vector<int>& memo, int n) {
// base case
if (n == 1 || n == 2) return 1;
// 已经计算过
if (memo[n] != 0) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
由于本算法不存在子问题的计算，子问题就是f(1),f(2),f(3),...f(20)，数量和N成正比,所以子问题个数为O(N)。
这种解法是自顶向下的，而动态规划的解法是自底向上的。即先计算f(1)和f(2)开始往上推，直到最终问题的答案f(20)。
2.4 dp数组的迭代解法
有了上一步“备忘录”的启发，我们可以把这个“备忘录”独立出来成为一张表，就叫做
DP table吧。
int fib(int N){
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
vector<int> dp(N + 1， 0);
// base case
dp[1] = dp[2] = 1;
for (int i=3; i<=N; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[N];
}
这里引出了“状态转移方程”这个名词，实际上就是描述问题结构的数学形式:
f(n)=\left\{\begin{aligned}
1,n=1,2 \\
f(n-1) + f(n-2), n>2
\end{aligned}
\right.
其实当前状态只跟前边两个状态相关，所以只需要保存前两个即可，即只需要保存f(n-1)和f(n-2)。所以代码可以优化为:
int fib(int N){
if( N == 0 ) return 0;
if( N == 1 || N == 2) return 1;
int prev = 1, curr = 1;
for(int i = 3; i<=N; i++){
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
这个技巧就是所谓的“状态压缩”，如果我们发现每次状态转移只需要DP table中的一部分，那么可以尝试使用状态压缩来缩小DP table的大小，只记录必要的数据。
3. 凑零钱问题
先看下题目:给你k种面值的硬币，面值分别为c1,c2,..., ck，每种硬币的数量无限，再给一个总金额amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回-1。
算法的函数签名:
// coins中是可选硬币面值，amount是目标金额
int coinChange(int[] coins, int amount);
比如k=3,面值分别为1、2、5，总金额amount=11，那么最少需要3枚硬币凑出，即11=5+5+1。
3.1 暴力递归
首先是最困难的一步，写出状态转移方程，这个问题比较好写：
其实，这个方程就用到了「最优子结构」性质：原问题的解由子问题的最优解构成。即 f(11) 由 f(10), f(9), f(6) 的最优解转移而来。
public static int coinChange(List<Integer> coins, int amount){
if (amount == 0) return 0;
int ans = Integer.MAX_VALUE;
for (int coin : coins){
if ((amount - coin) < 0) continue;
int subResult = coinChange(coins, amount - coin);
if (subResult == -1) continue;
ans = Math.min(ans, subResult + 1);
}
return ans == Integer.MAX_VALUE ? -1: ans;
}
3.2 带备忘录的递归算法
public static int coinChangeMap(List<Integer> coins, int amount){
if (amount == 0) return 0;
int ans = Integer.MAX_VALUE;
for (int coin : coins){
if ((amount - coin) < 0) continue;
int subResult = 0;
if (result.containsKey(amount)){
subResult = result.get(amount);
}else {
subResult = coinChangeMap(coins, amount - coin);
}
if (subResult == -1) continue;
ans = Math.min(ans, subResult + 1);
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
3.3 dp数组的迭代解法
public static int coinChangeDP(List<Integer> coins, int amount){
int[] dp = new int[amount+1];
Arrays.fill(dp, amount+1);
dp[0] = 0;
//外层for循环遍历所有状态取值
for (int i=1; i < dp.length; i++){
//内层循环求所有选择的最小值
for (int coin : coins){
//子问题无解，跳过
if ((i - coin) < 0) continue;
dp[i] = Math.min(dp[i] , 1 + dp[i-coin]);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
参考资料
- 《labuladong的算法小抄》
