动态规划的基本思想在于发现和定义问题中的子问题，这里子问题可也以叫做状态；以及一个子问题到下一个子问题之间 是如何转化的 也就是状态转移方程
因此我们遇到一个问题的时候 应该想一想这个问题是否能用某种方式表示成一个小问题，并且小问题具有最优子结构
最优子结构：问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解
关于最优子结构 我们来看2个示例
1、求无权有向图中q-t的最短路径
如果q-t间的最短路径经过了点w 那么我们可以证明 q-w w-t也均是最短路径
所以无权有向图最短路径是具有最优子结构的
网友评论
