2020.1.20 主讲 GodofTheFallen

动态规划入门

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

概念

阶段

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

决策

决策是一个集合。不同的状态可能有不同的决策集合。但是同一个状态一定有相同的决策集合。

状态

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

最优解&最优子结构

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

记忆化搜索

模板

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=0~1,则更倾向于1D而不是2D 转移的维数

拓扑序DP是啥

递推式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))}`

【笔记】动态规划入门

原文：https://www.cnblogs.com/ZhengkunJia/p/12219154.html