简介
用于解决多阶段决策过程的最优化问题。
动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。
动态规划（以后简称 dp）是一种运筹学的思想，在运算角度的意义就在于通过记录有用的值供以后的运算调用，从而减少了重复运算，提高了效率。
从程序设计来说主要通过递推或记忆化搜索来实现 dp 算法。
案例分析
动物运输
怎样才能让单次运输价值最大？
第一辆车载重 第二辆车载重 。
| 品种 | 重量（每只） | 价值 |
|---|---|---|
| 狼 | ||
| 豹 | ||
| 虎 |
显然我们想到了贪心，但贪心不一定是正确的。
贪心：每一步都取当前最优解，当问题求解结束时，得到最优解。实际上最后的解是由之前的每一步合并而来。这样的问题符合最优子结构。
最优子结构：指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。
贪心正确性：最优子结构 + 严格证明。
在第二辆车载重是 的情况下，虽然虎的单位价值最高但在其他约束条件下，并不是最优的，如果先把虎放进车，就排除了把两只狼放入车的方案，从而导致求解失败。实际上这个问题符合最后子结构，经过分析却不能使用贪心求解。
dp 应用条件总结
最优子结构：部分解合并成最优解。
无后效性：不走回头路。
如果具有重叠子结构 可以通过递推和记忆化搜索来设计 dp。
边界（已知，未知），是个由已知推未知的过程。一般具有明显方向性，特定情况下才可逆。
与贪心比较
从某种角度上看贪心可以看做一种特殊的 dp，每个阶段却只能保留一个状态值，对于同一阶段有多个状态点的问题，有些情况下就会错误。
杂项
疯狂加维，谨慎减维。
如果遇见选择或者不选择状态的题目时，可以考虑背包。
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/fb97362d0c35/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
