动态规划的算法策略必须要从数学上的某个定理说起:
如果某个决策满足最优化,那么在这个决策的某个阶段性状态下,它的基于当前状态下的剩余决策也是最优的。
如果一个决策在任一阶段性状态下,它的基于当前状态下的剩余决策总是最优的,那么这个决策在整体上是最优的。
这里面有几个非常要注意的条件:
a:首先我们要确定我们的问题是在基于多阶段的情况下
b:问题是在多阶段下寻求某种最优的状态
c:需要验证上面定理的判定是正确的
在基于上面的数学思想建立算法的时候,每个决策阶段都是基于以前的决策进行计算的,所以每个阶段都不是相互独立的,都需要基于以前的决策进行计算,计算的过程中会多次使用以前阶段的计算结果。为了方便称呼,多次结算的阶段称为重叠子问题。最优决策的每个阶段都是基于当前状态下的剩余决策最优称为最优决策的最优子结构性质。算法的关键是通过记录最优子结构的计算结果来避免重复计算来降低算法的时间复杂度,但是由于保存最优子结构的计算结果,算法的空间复杂度在升高