动态规划的深入讨论

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