动态规划的技巧——阶段的划分和状态的表示
在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的两
步，这两步会直接影响该问题的计算复杂性，有时候阶段划分或状态
表示的不合理还会使得动态规划法不适用。
[例 9]街道问题
在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方
走。
这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章
中都拿它来做例子。通常，书上的解答是这样的：
按照图中的虚线来划分阶段，即阶段变量 表示走过的步数，而状态
变量
表示当前处于这一阶段上的哪一点。这时的模型实际上已经转
剩余10页未读，继续阅读
评论0