动态规划知识简记

一、基本概念

1、定义

动态规划（Dynamic Programming）：简称 DP，是一种求解多阶段决策过程最优化问题的方法。在动态规划中，通过把原问题分解为相对简单的子问题，先求解子问题，再由子问题的解而得到原问题的解。

2、核心思想：

把原问题分解为若干个重叠的子问题，每个子问题的求解过程都构成一个阶段。在完成一个阶段的计算之后，动态规划方法才会执行下一个阶段的计算。

二、特点

1、与贪婪算法相比

动态规划一定程度弥补贪婪算法的缺点，能找到最优解

2、与分治算法相比

适用于动态规划求解的问题，在分解之后得到的子问题往往是相互联系的，会出现若干个重叠子问题。这与分治算法不同

使用动态规划方法会将这些重叠子问题的解保存到表格里，供随后的计算查询使用，从而避免大量的重复计算

每种动态规划都涉及到表格（网格），每个单元格是一个子问题，单元格里的值是子问题的解，通常也是要优化的值，如何将问题分解为子问题是动态规划的一个核心问题。

三、使用条件

能够使用动态规划方法解决的问题必须满足以下三个特征：

1、最优子结构性质

问题的最优解包含其子问题的最优解

2、重叠子问题性质

在求解子问题的过程中，有大量的子问题是重复的，一个子问题在下一阶段的决策中可能会被多次用到。如果有大量重复的子问题，那么只需要对其求解一次，然后用表格将结果存储下来，以后使用时可以直接查询，不需要再次求解。

3、无后效性

子问题的解（状态值）只与之前阶段有关，而与后面阶段无关。当前阶段的若干状态值一旦确定，就不再改变，不会再受到后续阶段决策的影响，一旦某一个子问题的求解结果确定以后，就不会再被修改。

四 步骤（思路）

1、划分阶段：

将原问题按顺序（时间顺序、空间顺序或其他顺序）分解为若干个相互联系的阶段。

划分后的阶段⼀定是有序或可排序的，否则问题⽆法求解。

阶段指的是⼦问题的求解过程。每个⼦问题的求解过程都构成⼀个阶段，在完成前⼀阶段的求解后才会进⾏后⼀阶段的求解。

2、定义状态：

将和子问题相关的某些变量（位置、数量、体积、空间等等）作为一个状态表示出来。

状态要满⾜⽆后效性。

一个状态对应一个或多个子问题，所谓某个状态下的值，指的就是这个状态所对应的子问题的解。

3、状态转移：

根据上一阶段的状态和该状态下所能做出的决策，推导出下一阶段的状态。或者说根据相邻两个阶段各个状态之间的关系，确定决策，然后推导出状态间的相互转移方式（即状态转移方程）。

4、初始条件和边界条件：

根据问题描述、状态定义和状态转移方程，确定初始条件和边界条件。

5、求解

确定问题的求解目标，然后按照一定顺序求解每一个阶段的问题。最后根据状态转移方程的递推结果求解问题。