动态规划

什么是动态规划 (Dynamic Programming) 简称 DP

动态规划, 擅长解决多阶段决策问题, 利用各个阶段的递推关系, 逐个确定每个阶段的最优决策, 并最终得到原问题的最优策略

举个例子: 10 级台阶, 每次可以上 1 级也可以上两级, 问上完一共有多少种可能?

这个问题可以反向思考, 到第 10 阶有哪些办法? 第 8 阶+2 或者第 9 阶+1, 也就是, 第 10 阶的办法=第 9 阶的方法数+第 8 阶的方法数

F(10) = F(9) + F(8)

最优子问题 F(10) = F(9) + F(8), 就是 F(10) 问题的最优解, 局部的贪心完美的将问题分解, 如果 F(9)和 F(8)都是最优解, 那么 F(10)一定也是最优解了

边界条件分解到最后, 一定会变成 F(1), F(2) 这样的规模最简单的问题, 这两个问题不能再分解了

状态转移方程 (DP 方程) 上面问题的状态转移方程为 F(n) = F(n-1) + F(n-2), 这就是解决问题的核心, 能够让状态动起来

状态使用表格储存起来, 实际上的 DP 是从简单问题往复杂问题变化的

最优子问题不管之前的决策是否为最优的, 都必需保证从现在开始的决策是在之前的基础上最优. 具体来说, 我们默认 F(8), F(9) 是最优的, 在此基础上, 得到最优的 F(10)

不影响后续决策由上一条可以看到, 如果 F(8)的决策会影响到 F(9)和 F(10)的决策, 那么 F(10)=F(8) + F(9)就不成立, 所以, 要一定保证每个觉得的决策仅受之前决策的影响, 但不影响之后的决策

我们可以使用贪心算法得到一个解, 但是不能保证得到的是最优解, 而 DP 可以得到最优解

状态方程: s[i, j] = max{s[i-1, j], s[i, j-vi] + pi}

其中 vi 代表第 i 件物品所占体积, pi 表示第 i 件物品的价值

动态规划是一种能够求解出全局最优解的算法, 所以其实相当于穷举搜索了所有的解空间, 但是为什么高效呢? 是因为使用了储存备忘录的方式, 相当于使用了剪枝判断, 对重复子问题完成了高效的处理