动态规划
不知道大家有没有听说这样的说法
贪心：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边；
回溯：一条路走到黑，无数次重来的机会，还怕我走不出来；
动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来；
因此动态规划是一种很好用的算法。
经典的动态规划问题：0-1背包、0-1背包升级版、青蛙跳变态版、棋盘的最小路径等。
什么时候可以用动态规划？
虽然说有一个模型三个特征，但个人还是通过一个流程来判断是否可以使用动态规划。
【注】一个模型：多阶段决策最优解模型
三个特征：最优子结构、无后效性和重复子问题
个人总结流程
我们假设背包的最大承载重量是 9。我们有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少？
看问题判断：
- 找最优解
- 是否多阶段
画递归树：
- 从第一个阶段开始（根节点），观察有多少种决策可以选择。
- 从第二个阶段开始（子树），从观察有多少种决策可以选择。
- 好，停。这时候你就大概会有一种感觉，就是”重复“。
如上图是0-1背包问题的递归树，递归树中的每个节点表示一种状态，我们用（i, cw）来表示。其中，i 表示将要决策第几个物品是否装入背包，cw 表示当前背包中物品的总重量。
PS.图参考自王争《数据结构与算法之美》
画状态转移表：
- 先画二维的状态转移表；（这里行列数代表的意义要明确）
- 手工填一部分状态转移表；
- 找到状态转移的规律；
- 总结出状态转移状态方程；
代码实现
weight: 物品重量，n: 物品个数，w: 背包可承载重量
public int knapsack(int[] weight, int n, int w) {
boolean[][] states = new boolean[n][w+1]; // 默认值 false
states[0][0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
states[0][weight[0]] = true;
for (int i = 1; i < n; ++i) { // 动态规划状态转移
for (int j = 0; j <= w; ++j) {// 不把第 i 个物品放入背包
if (states[i-1][j] == true) states[i][j] = states[i-1][j];
}
for (int j = 0; j <= w-weight[i]; ++j) {// 把第 i 个物品放入背包
if (states[i-1][j]==true) states[i][j+weight[i]] = true;
}
}
for (int i = w; i >= 0; --i) { // 输出结果
if (states[n-1][i] == true) return i;
}
return 0;
}
多写多练，就能有自己的一套方法和技巧。
推荐从0-1背包和青蛙跳变态版开始练。
补充
还有的动态规划问题，是从多个“方向”而来。
如棋盘的最短路径问题：
假设我们有一个 n 乘以 n 的矩阵 w。矩阵存储的都是正整数。棋子起始位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
那么他就会从两个方向来，只有可能从 (i, j-1) 或者 (i-1, j) 来。
因此状态转移表变成下图
我的动态规划之路还有很多要学，大家一起进步！
