博学笃志切问近思!

今天在队长李亭乐的带领下我们学习了算法——动态规划，在一开始给我们分发试题，然后进行题后分析，最后把每个人的学到的知识总结在一起，让每个成员都能深入了解动态规划。

一、动态规划的概念

动态规划是分治思想的延伸，通俗一点就是大事化小，小事化无的艺术。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。

二、动态规划的思想

1.原问题分解成为子问题：子问题一旦求解出来，我们就要保存，避免重复计算

2.确定状态：一般为多维数组来进行存放

3.确定一些初始状态（边界状态值）

4.写出状态转移方程

将已求解的各个子问题的解，逐步合并为原问题的解。

三、动态规划的优缺点

动态规划的优点：

1.能够得到全局最优解。

2.可以得到一族最优解。

3.由于动态规划方法反映了动态过程演变的联系和特征，在计算时可以利用实际知识和经验提高求解效率。

动态规划的缺点：

1.没有统一的标准模型。

2.数值方法求解时存在维数灾。（需要额外的内存空间，并且一维问题可能需要二维空间）

四、动态规划的步骤

（1）找出最优解的性质，并且刻画其结构特征

（2）递归地定义最优值

（3）以自底向上的方式，将问题分解为各个小问题，一步步地计算出最优值

（4）根据计算最优值时得到的信息，构造一个最优解

希望每个人不忘初心，三省吾身，积极进取，迎难而上！要始终记得博学而笃志，切问而近思！

http://www.dxsbao.com/shijian/462332.html 点此复制本页地址