动态规划 术语¶
前置知识¶
动态规划经验问题入门
目标¶
上点科技狠活
动态规划的用途¶
Dynamic Programming is a technique that combines the correctness of complete search and the efficiency of greedy algorithms. Dynamic Programming can be applied if the problem can be divided into overlapping subproblems that can be solved independently. There are two uses for Dynamic Programming:
- Finding an optimal solution: We want to find a solution that is as large as possible or as small as possible.
- Counting the number of solutions: We want to calculate the total number of possible solutions.
理论基础¶
我们之前探讨过的很多算法，都是利用问题的可划分性以及子问题之间的相似性来进行归纳，降低求解的复杂度，动态规划也不例外。动态规划把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。
从“状态空间”入手对“问题与状态空间”之间的类比，有了更深入的认识。
- 递推和递归是两种遍历状态空间的基本方法
- 搜索算法，处理指数级别等非多项式复杂度的问题
- 动态规划算法，针对满足特定条件的一类问题，对各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解
动态规划，把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个“阶段”。
在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。
为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响（如果没有先后，谁推导谁就会混乱。这个名词叫做“无后效性”）。
本质上，动态规划对状态空间的遍历，构成了一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序（有向无环图中的node，对应问题中的“状态”。图中的edge对应状态之间的“转移”，转移的选取就是动态规划中的“决策”）。
动态规划用于求最优解的问题时，下一阶段的最优解应该能够由前面各阶段子问题的最优解导出。这个条件被称为"最优子结构性质"（当子结构之间都可以用代表元素和最优解来推导时，称问题满足最优子结构性质）。
在阶段计算完成时，动态规划只会在每个状态上保留与最终解集相关的部分代表信息，这些代表信息应该具有可重复的求解过程，并能够导出后续阶段的代表信息。这样一来，动态规划对状态的抽象和子问题的重叠递进才能够起到优化作用。
- 状态、阶段、决策是构成动态规划算法的三要素
- 子问题重叠性、无后效性、最优子结构是问题能用动态规划求解的三个基本条件
动态规划算法把相同的计算过程作用于各阶段的同类子问题，就好像把一个固定的公式的格式相同的若干输入数据上运行。定义出了动态规划的计算过程，就可以编程实现了，这个计算过程被称为“状态转移方程”。
动态规划的描述框架¶
总结¶
具有线性 “阶段” 划分的动态规划算法被称为线性DP，无论状态表示是一维还是多维，DP算法在这些问题上都体现为“作用在线性空间上的递推”——DP的阶段沿着各个维度线性增长，从一个或多个“边界点”开始有方向地向整个状态空间转移、扩展。最后，每个状态上都保留了以自身为“目标”的子问题的最优解。
在LIS、LCS、数字三角形，这些经典问题中，需要计算的对象表现出明显的维度以及有序性，每个状态的求解直接构成一个阶段，这使得DP的状态表示就是阶段的表示。
因此，我们只需要在每个维度上各取一个坐标值作为DP的状态，自然就可以描绘出“已求解部分”在状态空间中的轮廓特征，该轮廓的进展就是阶段的推移。
另外，每个状态的求解，显然只与之前阶段的最有解有关，“最优子结构”性质也得以验证。接下来，我们按顺序依次循环每个维度，根据问题要求，递推求解的具体实现过程也就顺理成章了。
参考¶
《算法竞赛进阶指南》