首页 > 代码库 > [专题]动态规划的总结和体会

[专题]动态规划的总结和体会

能用动规解决的问题的特点
1) 问题具有最优子结构性质。如果问题的最优解所包含的
子问题的解也是最优的,我们就称该问题具有最优子结
构性质。
2) 无后效性。当前的若干个状态值一旦确定,则此后过程
的演变就只和这若干个状态的值有关,和之前是采取哪
种手段或经过哪条路径演变到当前的这若干个状态,没
有关系。

尤其是第二点无后效性,感觉和阶段划分的方式有关(个人猜测),动态规划解的这几道题,题解上面的阶段划分方法都挺意想不到的。