前言
最近和朋友聊天，说起DP问题，想到大学时候学长上来一通“状态转移函数”把我们讲懵了，于是尝试写个入门笔记。
DP思想
通俗来说，动态规划解决问题的方法，就是当系统处于任何一个状态C，你去穷举所有状态A，然后把可能从A到达C的情况全部找出来，并从中获得最优解即可。所以，所谓的“状态转移方程”就是存在一条边从状态A到状态C，这条边的代价。简而言之，动态规划主要思想就是自底向上、局部最优到全局最优，通过计算每个子结构的最优解，求出总体结构的最优解。其目的是解决通过自顶向下的算法（如递归），带来的子结构重复计算，导致时间复杂度指数级上升的问题。
入门示例
桌上有 1kg、8kg、11kg 的三种砝码不限量供应，如何用最少数量砝码凑出 17kg 的量？
分析
设最少需要 n 个砝码，可以凑出 17kg 的量，设方程 f(x) 表示求 x(kg) 的量最少需要多少个砝码，那么我们有 ：f(17kg) = n。
现在，我们从 17kg 砝码中拿走一个，由于整体是最优的，所以子结构一定是最优的，即剩下的重量和砝码数量也一定满足我们的 f(x)。于是，我们一定有： min{f(17kg - 1kg), f(17kg - 8kg), f(17kg - 11kg)} = n - 1。
所以，我们从已知结果 f(1kg) = 1、f(8kg) = 1、f(11kg) = 1 开始向上计算，直到 x 抵达 17kg即可。
计算过程
f(0) = 0
f(1kg) = 1
f(2kg) = f(1kg) + f(1kg) = 2
f(3kg) = f(2kg) + f(1kg) = 3
f(4kg) = f(3kg) + f(1kg) = 4
f(5kg) = f(4kg) + f(1kg) = 5
f(6kg) = f(5kg) + f(1kg) = 6
f(7kg) = f(6kg) + f(1kg) = 7
f(8kg) = 1
f(9kg) = min{f(8kg) + f(1kg), f(1kg) + f(8kg)} = min{2, 2} = 2
f(10kg) = min{f(9kg) + f(1kg), f(2kg) + f(8kg)} = min{3, 3} = 3
f(11kg) = 1
f(12kg) = min{f(11kg) + f(1kg), f(4kg) + f(8kg), f(1kg) + f(11kg)} = min{2, 5, 2} = 2
f(13kg) = min{f(12kg) + f(1kg), f(5kg) + f(8kg), f(2kg) + f(11kg)} = min{3, 6, 3} = 3
f(14kg) = min{f(13kg) + f(1kg), f(6kg) + f(8kg), f(3kg) + f(11kg)} = min{4, 7, 4} = 4
f(15kg) = min{f(14kg) + f(1kg), f(7kg) + f(8kg), f(4kg) + f(11kg)} = min{5, 8, 5} = 5
f(16kg) = min{f(15kg) + f(1kg), f(8kg) + f(8kg), f(5kg) + f(11kg)} = min{6, 2, 6} = 2
f(17kg) = min{f(16kg) + f(1kg), f(9kg) + f(8kg), f(6kg) + f(11kg)} = min{7, 3, 7} = 3代码实现
const dp = (X) => {
const result = [];
for (let x = 0; x <= X; x++) {
if (x === 0) {
result[x] = 0;
} else if (x === 1 || x === 8 || x === 11) {
result[x] = 1;
} else if (x < 8) {
result[x] = result[x - 1] + 1;
} else if (x < 11) {
result[x] = Math.min(result[x - 1] + result[1], result[x - 8] + result[8]);
} else {
result[x] = Math.min(result[x - 1] + result[1], result[x - 8] + result[8], result[x - 11] + result[11]);
}
}
return result[X];
}
console.log(dp(17)); // 3示例思考
优化
上述示例中，我们发现 result 表实际上不需要全部保存，每次状态转移计算 f(x) 只需要最多获取历史记录值 f(x - 11)，所以我们不需要保存 f(1) ~ f(x - 12) 部分的计算结果。
局限
上述示例中，状态转移函数都是获取历史结果，即砝码重量不存在负数，也就是 f(x) 不存在回溯的情况，否则不再适用。
扩展
针对上述局限，假设我们有一个砝码从异次元拿来，重量为 -1kg，同时我们加入一个 18kg 的砝码同时去掉 8kg的砝码，那么最少需要几个砝码可以获得16kg重量呢？
答案很简单，动态规划结合深度优先搜索即可（部分场景下问题需要结合二分查找）。
和之前的计算逻辑一样，从 x = 0 开始计算 f(x)，不同的是，在每个节点 x，我们从该节点出发进行 DFS 搜索，即搜索 +1、+11、+18、-1 五种搜索路径。类似上文，通过状态转移方程依次计算，这里我们需要额外记录下搜索到每个点的步数（也就是砝码数量），当搜索到 x 时，如果记录的搜索步数已经大于当前 f(x) 则返回，因为当前搜索已经不是最优，继续搜索也没有意义了。
代码实现
const dp = (X) => {
const dir = [1, 11, 18, -1];
const result = [0];
const MAXN = 10000;
// 开始 DFS 搜索，这里不能用递归否则会爆栈
const dfs = [{ weight: 0, count: 0 }]; // 砝码重量，砝码数量
while (p = dfs.pop()) {
for (let i = 0; i < dir.length; i++) {
const weight = p.weight + dir[i];
if (weight <= MAXN && weight >= 0) {
const count = p.count + 1;
if (result[weight] === void 0 || result[weight] > count) {
result[weight] = count;
dfs.push({ weight, count });
}
}
}
}
return result[X];
}
console.log(dp(16)); // 3版权属于：一名宅。
本文链接：https://zhaiyiming.com/archives/dynamic-programming.html
转载时须注明出处及本声明
收藏了hhhc