动态规划 » 老官童鞋gogo的博客

动态规划简介

动态规划是理查德·贝尔曼与$1957$年提出的一种方法，他把原问题分解成若干个小问题，自底向上先求解最小的子问题，把结果存储在表格中，求解大的子问题时直接从表格中查询小的子问题的解，以免重复计算，从而提高效率。

最优子结构是指问题的最优解包括其子问题的最优解。

子问题重叠指的是每次分解出来的子问题并不总是新问题，例如在求斐波那契数列时，会不断调用前面所求出来的答案。如果每次分出来的问题总是新问题，那么这种动态规划就相当于是暴力枚举。

无后效性指在求解出子问题后，子问题不会受到后面求出来的答案的影响，而改变子问题的答案，也就是说，求解的答案只与前阶段有关而与后阶段无关，在求解后面的问题直接用就可以，否则这种动态规划是错误的。

有关动态规划的问题，通常来讲，它的思维难度更高，代码难度很低，考察到思维的严谨性。

阶段、状态、决策是动态规划的三个要素。

动态规划将原问题划分为多个子问题，通过求解子问题的解得到原问题的解，每个子问题的求解过程都构成一个阶段，在完成前一阶段的求解后才会进行后一阶段的求解。

既然要将子问题的答案传递给原问题，就要考虑究竟要传递那些信息，用什么样的方式去表示这些信息，表示信息的方式就叫做状态。

做好阶段与状态的准备，就要考虑解决问题的方法，即如何将前一位的状态转移给后一位，实现状态转移。

通过上述的例子，我们归纳一下动态规划的设计方法：

动态规划一般分为一下步骤：

按照问题的时间特征和空间特征，将子问题划分为若干个阶段。划分后的阶段一定是有序或者是可以排序的，否则问题无法求解。

将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来，确定状态和状态变量。当然，对状态的选择要满足无后效性。

状态转移指根据上一阶段的状态和决策导出本阶段的状态。根据相邻两阶段各个状态之间的关系确定关系的决策，一旦确定决策，就可以写出状态转移方程，问题至此，答案基本生成。

状态转移方程总是会有边界的，因为一个状态总是转移过来的，如果没有初始的确定的状态，就不会出现转移。

在经过一系列的问题处理后，答案就在最终产生的状态中，我们需要根据问题的要求，对状态进行处理，例如最大值、极差等等，整理最终答案。

直接用文字说明定义、过程会有些抽象，下面举出一个实例来解释。例如求解斐波那契数列的第n项：

首先我们猜想问题的解决方案，然后确定这个问题的解决方法符不符合动态规划的性质：

根据其数学原理可知，斐波那契的第$n$项$(n \ge 3)$都等于前两项的和，由此说明了这个问题具有最优子结构，因为我们会重复调用之前求出的$(n-1)$项答案和$(n-2)$项的答案，说明问题具有子问题重叠的性质，其次，当我们计算出了第$n$项，这一项的答案在之后的求解过程中不会再改变，这说明该问题存在无后效性。所以我们可以根据其数学原理进行动态规划。
然后根据我们的解决方案思考其三要素：
- 根据解决方案确定状态，这是最重要的一步，如果状态设置错误，下面的所有过程都是错误的。对于这个问题，设$dp[i]$表示斐波那契数列中第$i$项的值。
- 对于阶段的分化，在思考问题的解决方法中已经体现。对于求解这个问题，我们要从小项计算到大项，因为每一项都是由前两项相加计算得出的。
- 到了决策层面，我们要根据解决问题的方法与状态设置转移方程，很显然，这道题的转移方程为：$dp[i]=dp[i-1]+dp[i-2]$。除了转移方程，我们要考虑动态规划的边界与初始值，根据斐波那契数列的特殊性，第$1$项与第$2$项是直接定义的，均为$1$，由此在进行方程转移时，要提前赋值dp[1]=dp[2]=1。对于边界，它并没有上界，可以无限计算。