【笔记】动态规划入门

2020.1.20 主讲 GodofTheFallen

动态规划入门

dp，递归，递推，搜索，记忆化？

概念

动态规划（DP）

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

动态规划被用于解决多阶段最优化决策问题。它的基本思路是将待解决的问题划分成多个阶段，每个阶段可能存在多种不同的状态。如果划分阶段后的问题满足最优子结构，则可以用动态规划算法一个阶段一个阶段，一个状态一个状态地解决问题的所有子问题，继而解决原问题。

阶段

阶段的划分是人为的。但是必须满足在一个阶段的任意状态做出任何决策后，得到的新状态都属于之后的阶段。（甚至不能在原阶段停留）
不过实际问题中，有的时候阶段并不是线性的，有的时候你很难描述阶段，但是实际上阶段只是提供了一个解决问题的顺序和设计状态的思路，设计出合理高效的状态才是解决问题的关键。

即：阶段的最大作用是辅助状态设计。

设计的状态必须要 满足程序分析的无后效性，这很重要

决策

决策是一个集合。不同的状态可能有不同的决策集合。但是同一个状态一定有相同的决策集合。
理解为选择即可

状态

应描述一个事件，并且包含一切会对决策产生影响的限制条件

转移

从一个状态到另一个状态，就是转移

最优解&最优子结构

能动态规划解决的问题必须满足——任何一个子问题的最优解，做出第一步决策之后，剩下的决策集合仍然是转移到的子问题的最优解。这一条件叫做最优子结构。
这个条件也有等价描述如——
每个子问题的解与转移到它所经历的决策互不影响。（无后效性）

以上概念不用记的QAQ

记忆化搜索

模板

int Solve(子问题)
{
    if (子问题已求解) return 记录的结果;
    枚举每一个可以转移来的子问题 Solve(这些子问题),更新当前答案;
    记录答案;
    return 答案;
}
//主程序中
枚举每一个子问题 Solve(该子问题);

用数组存答案，避免重复计算，每一个状态只用O（1）查询子问题的答案

优点：

1. 普适性极强，所有满足最优子结构的问题都可以用记忆化搜索解决，不必要按阶段顺序求解，甚至不必要划分阶段
2. 有的题目中一些小规模的子问题不会对最终答案有贡献，记忆化搜索不会对这些问题求解
3. 思路直接，是正常的分析问题解决问题思路，不需要太多推导

缺点：

1. 在函数调用时需要消耗一定时间，而且递归层数过多可能造成栈空间超限
2. 代码实现上稍微复杂一些（代码量大些）
3. 程序结构复杂，不利于优化

例题

【DAG最大值】
递推比递归快

【乘积最大】

solve(n,k) = max {solve(i , k - 1)*num(i + 1 , n} 问题转化为 这个乘号之前的序列 添加k - 1个乘号的最大乘积子问题

分析算法

dp的维数
状态的维数
需要的变量数，大多数情况下可认为是递推数组的维数 不过有时候比如f[i][j],i=1_n,j=01,则更倾向于1D而不是2D 转移的维数

拓扑序DP是啥

Solve(x)表示从节点x出发（不要求x是出发点）到某个结束点的链权值最大值。
W(x)表示x的点权，w(<x,y>)表示<x,y>弧的边权
Solve(x)=max( {W(x)+w(<x,y>)+Solve(y) | <x,y>存在}∪{-INF} )
如果x是结束点，则再与W(x)求max
主程序中
枚举每一个开始点，ans=max(ans,Solve(开始点));

这是其实你会发现，有一些从开始点出发无法到达的点对应的子问题不需要也根本不会被求解

其实，DAG在动态规划中是一个非常关键的概念
如果我们将问题中所有的状态看成点集V,所有转移看成有向边集E
如果G={V,E}为一个DAG，那么这个问题就可以动态规划解决
或者说，至少可以用记忆化搜索式动态规划解决
具体做法是
对于每个点，求出所有需要转移到的子问题的最优解，然后算上转移时决策的影响，优化当前点的解，已求出解的问题保存下来再次求解时直接返回
然后从每个合法初始状态出发调用一次求解函数
当然反图的BFS也是可取的

（详细解释我过会再补）

递推式DP

优点：

1. 代码简短，运行常数小
2. 方便概括，程序结构清晰，易于发现优化

缺点：

1. 需要一定的推导，有一定的思维难度
2. 每一个状态都会被求解，无法排除无效状态,难优化

鬼东西

状态转移方程

[f[U]=max/min{R(f[&cigema-1U],g(&cigema,cigema-1U))} ]

状态转移方程

[f[U]=max/min{R(f[&cigema-1U],g(&cigema,cigema-1U))} ]

状态转移方程

[f[U]=max/min{R(f[&cigema-1U],g(&cigema,cigema-1U))} ]