【摘要】
    本文讨论了一种解决问题十分有效的技术——“动态规划”。它较高的解题效率一直受到很大的关注。本文首先对“动态规划”的理论基础进行了讨论。给出了一个用“动态规划”可以解决的问题的两个先决条件：“最优子结构”与“无后效性”。接着，讨论了在实际应用中的两个比较常见的问题：“动态规划”中状态的选定与存储。再通过以上问题的讨论，引出了“动态规划”的基本思维方法：“不做已经做过的工作”以及“动态规划”技术在解决问题中速度惊人的原因——“解决了查看中的冗余，达到了速度的极限”。最后，阐述了解决“动态规划”问题的一般步骤，即“思考，计划，应用”。
【关键字】  动态规划、状态

目录
动态规划的深入讨论 1
【摘要】 1
目录 2
一．引 论 3
二．动态规划的理论基础 6
一：最优子结构 6
二：无后效性 7
三．动态规划的实际应用 9
1：状态的选定： 9
2：状态的存储 10
四．动态规划的深入思考 13
五．总结 15
【参考书目】 16

一．引 论
    在信息学竞赛中，特别是最近几年，“动态规划”作为一种解题工具，经常被提及。其应用范围愈来愈广，应用程度也愈来愈深。那么，“动态规划”究竟与其它的算法有什么差别？它有什么具体的应用价值呢？本文将对此进行讨论。
    我们先通过一个具体问题认识一下“动态规划”。
   〖例1〗：图1中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少？