标签：动态 凑出 基础 step 背包 序列 例题 规划 dp
引入
动态规划简介
- 动态规划 \(dp=Dynamic \ Programming\)
- 线性 \(dp\)：状态定义与题设线性相关
- 将原问题分解成若干子问题
- 设计状态：状态是当前问题所在的局面
- 满足性质：无后效性，最优子结构
- 转移：状态之间的关系，用转移方程描述
- 动态规划（递推） 和 记忆化搜索（递归） 时间复杂度相同
- 记忆化搜索可以规避转移顺序，且方便处理边界情况
- 记忆化搜索效率较低，且难以优化、调试
例子：最长上升子序列
- 状态：以第 \(x\) 个元素结尾的最长上升子序列（\(LIS\)）的长度，用 \(f_x\) 表示
- 转移：最长上升子序列一定是接在某个上升子序列尾部形成的
- 刻画整体的转移路径：
- 把每一个状态视作一个节点，把状态转移视作一条有向边，串联起来构成有向无环图（\(DAG\)）
- 所以根据拓扑序对图进行遍历来求解问题（拓扑排序）
- 动态规划遍历顺序称为阶段
动态规划三要素
- 状态（描述问题局面）
- 转移（状态之间的数学关系）
- 阶段（计算状态的顺序）
B3635 硬币问题
- 题意简述：用 \(1, \ 5, \ 11\) 元的硬币凑出 \(n\) 元，最少需要多少硬币？
- 状态：\(dp_n\) 表示凑出 \(n\) 元所需要的最少硬币数量
- 转移：\(dp_i = min(dp[i-1], dp[i-5], dp[i-11]) + 1\)
- 解释：凑出 \(n\) 元有三种局面
- 凑出 \(n-1\) 元，拿出一个 \(1\) 元硬币
- 凑出 \(n-5\) 元，拿出一个 \(5\) 元硬币
- 凑出 \(n-11\) 元，拿出一个 \(11\) 元硬币
- 取三个当中的最小值
一维线性 \(dp\)
- 使用 \(dp\) 求出 LIS 和 LDS，枚举中间最高的那个人
优化最长上升子序列
- 第一种枚举时间复杂度 \(O(n^2)\)，但存在大量重复枚举
- 记录以前选的所有数的下标，对于元素 \(x\)
- 如果 \(x\) 小于最大值，那么替换掉第一个大于它的数
- 如果 \(x\) 大于最大值，那么插入到最后
- 优化后时间复杂度 \(O(n \ log \ n)\)
二维线性 \(dp\)
- 状态：设 \(f[i][j]\) 表示到了位置 \((i,j)\) 时可以得到的最大数字和
- 转移：\(f[i][j]=max(f[i-1][j-1], f[i-1][j])+a[i][j]\)
例子：最长公共子序列
- 给定两个序列 \(A,B\)，求最长公共子序列（\(LCS\)）的长度
优化前
- 状态：\(f[i,j]\) 表示第一个排列前 \(i\) 个元素和第二个排列前 \(j\) 个元素，最长公共子序列的长度
- 转移：$$f[i,j]=f[i-1][j-1]+1,A_i=B_j$$
\[f[i,j]=max(f[i-1][j],f[i][j-1]),A_i≠B_j
\]
\[f[i][j]=\begin{cases}
f[i-1][j-1]+1 & A[i]=B[j] \\
max(f[i-1][j],f[i][j-1]) & A[i]≠B[j]
\end{cases}
\]
优化后
- 重新标号：把 \(A\) 用字母标成单调递增数列，再用这样的标号标记 \(B\)，求 \(B\) 的最长上升序列
- \(f[step][a][b][x][y]\) 表示走了 \(step\) 步，甲走到 \((a,b)\)，乙走到 \((x,y)\)
- 把 step 一维省略：变为四维 dp
- \(f[step][a][b][x][y]=走到当前格对答案的贡献+\)
- \(f[step][a-1][b][x-1][y]\)
- \(f[step][a-1][b][x][y-1]\)
- \(f[step][a][b-1][x-1][y]\)
- \(f[step][a][b-1][x][y-1]\)
背包 \(dp\)
01 背包（一个物品只能选择一次）
- \(w\) 表示重量，\(v\) 表示价值，\(N\) 表示物品个数，\(W\) 表示背包容量，\(f\) 表示 \(dp\) 数组
- 注意：第二层循环必须从大到小枚举！
for (int i = 1; i <= N; i ++) {
for (int j = W; j >= w[i]; j --)
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
完全背包（每个物品可以无限次选择）
for (int i = 1; i <= N; i ++) {
for (int j = w[i]; j <= W; j ++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
多重背包（每个物品可以选择 \(k_i\) 次）
- 第一种：转换成 01 背包
- 第二种（二进制优化）：把每个 \(k\) 拆成二进制表示，即\(1+2+4+...+2^n\)，变成了 \(log \ k_i\)，再进行 01 背包
- 时间复杂度 \(O(nW\sum log \ k_i)\)
- 由于总时间有限，把完全背包的无限次转化为 \(1000\) 次
- 01 背包就是多重背包中的 \(k=1\)
- 物品被划分成 \(k\) 组，每一组内只能选择最多 \(1\) 个物品
- 组内先枚举物品重量，再内聚物品编号
- 共三维：组、重量、编号
- 每一种主件的四种情况
- 只购买主件
- 购买主件，附件 A
- 购买主件，附件 B
- 购买主件，附件 AB
区间 \(dp\)
区间 \(dp\) 介绍
- 在区间上做动态规划，求在区间上的最优解
- 区间 \(dp\) 的状态通常包括区间信息 \((l,r)\)
- 子区间信息满足区间加法
- 分治思想：大区间信息由小区间获得
区间 \(dp\) 例题：P1775
对环形问题的处理
- 使用破环成链的思想
- 将数组倍长，令 \(a[i+n]=a[i]\)
环上 \(dp\) 例题：P1063
- \(f[l][r]\) 表示将 \([l,r]\) 范围内全部能量珠合并释放的最大能量，可得 \(f[l][r]=max(f[l][k]+f[k+1][r]+a[l]×b[i]×b[r])\)
标签：动态,
凑出,
基础,
step,
背包,
序列,
例题,
规划,
dp
From： https://www.cnblogs.com/winter-tide/p/17608146.html