首先先引入一个例子:
无向图G有N个结点,它的边上带有正的权重值。求点A到点N的最短距离。
我觉得,动态规划的本质是递归,这样很容易判断一个问题是否能用动态规划法求解,因为只要思考将问题的规模缩小/扩大之后是不是用同样的方法求解即可。比如说N的前面有一个点N‘,则计算A到N’的最短距离本质上都是用一个相同的方法可以解决的。
再说说状态转移方程,这个是比较头疼的一个难点,我思考了之后觉得可以用通俗的语言来描述,这里假设和N点直接(注意是直接相连而不是有路径)相关的点是X,Y,Z,权值分别是x,y,z。要找到A到N的最短距离的必要条件是要到达N(这好像是废话(*^__^*) ),那我们就可以找到最终的状态转移方程是Min(Min(A,X)+x,Min(A,Y)+y,Min(A,Z)+z);(这里也很容易看出动态规划的本质是递归)。
动态规划就是把所有从目标A出发的最小值求出并存储(这点异常关键,这是它的性能大大优于递归的法宝,每个点只要关注和它有直接联系的点而不用重新从A开始进行判断),直到到达终点N。