动态规划

最优化原理

无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略的性质。通俗地讲就是子问题的局部最优将导致整个问题的全局最优。

无后效性原则

某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。无后效性,即”未来与过去无关”

最优子结构

大问题的最优解可以由小问题的最优解推出