动态规划
什么是动态规划 (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是从简单问题往复杂问题变化的
设计DP方程, 需要注意的点
- 最优子问题
不管之前的决策是否为最优的, 都必需保证从现在开始的决策是在之前的基础上最优. 具体来说, 我们默认 F(8), F(9) 是最优的, 在此基础上, 得到最优的F(10)
- 不影响后续决策
由上一条可以看到, 如果 F(8)的决策会影响到F(9)和F(10)的决策, 那么F(10)=F(8) + F(9)就不成立, 所以, 要一定保证每个觉得的决策仅受之前决策的影响, 但不影响之后的决策
典型应用
01背包问题
我们可以使用贪心算法得到一个解, 但是不能保证得到的是最优解, 而DP可以得到最优解
状态方程: s[i, j] = max{s[i-1, j], s[i, j-vi] + pi}
其中 vi代表第i件物品所占体积, pi表示第i件物品的价值
最长公共子序问题 (这一问题常被用于比较”相似度”)
动态规划为什么高效
动态规划是一种能够求解出全局最优解的算法, 所以其实相当于穷举搜索了所有的解空间, 但是为什么高效呢? 是因为使用了储存备忘录的方式, 相当于使用了剪枝判断, 对重复子问题完成了高效的处理
动态规划四个步骤
- 描述最优解的结构
- 递归定义最优解的值
- 按自底向上的方式计算最优解的值
- 由计算出的结果构造一个最优解