动态规划三要素
阶段，状态，决策
动态规划经典模型
LIS（最长上升子序列）
给定长度为 \(N\) 的序列 \(A[i]\)，求出其最长上升子序列的长度。（以不严格上升为例）
-
阶段：已经处理的序列长度 \(i\)
-
状态：\(f[i]\) 表示以 \(A[i]\) 结尾的 LIS 长度
-
转移
\[f[i]=\max\limits_{j\in\left[1,i-1\right]\wedge A[j]\leq A[i]}f[j]+1
\]
这个转移是 \(\Theta(N^2)\) 的。事实上可以通过二分来优化到 \(\Theta(N\log N)\)，但是不甚通用。
LCS（最长公共子序列）
给定长度为 \(N\) 的序列 \(A[i]\) 和长度为 \(M\) 的序列 \(B[i]\)，求出其 LCS 长度。
-
阶段：\(A\) 已经处理的长度 \(i\)，\(B\) 已经处理的长度 \(j\)
-
状态：\(f[i,j]\) 表示 \(A[1..i]\) 与 \(B[1..j]\) 的 LCS 长度
-
转移
\[f[i,j]=
\max\begin{cases}
\max(f[i-1,j],f[i,j-1]), \\
f[i-1,j-1]+1, \text{if } A[i]=B[j]
\end{cases}\]
时间复杂度 \(\Theta(NM)\)。
新手动态规划合集题单题解
P1359 租用游艇
给定从 \(i\) 到 \(j\) 的代价 \(w[i,j]\)（\(i\lt j\)），求出从 \(1\) 地到 \(N\) 地的最小代价。
设 \(f[i]\) 表示从 \(1\) 到 \(i\) 的最小代价。转移方程：
\[f[i]=\max\limits_{j\in[1,i-1]}\left(f[j]+w[j,i]\right)
\]
初值：\(f[1]=0\)，其余均为正无穷。目标：\(f[n]\)。
P1060 [NOIP2006 普及组] 开心的金明
有 \(n\) 元，\(m\) 个物品。第 \(i\) 个物品价值为 \(v[i]\)，权值为 \(w[i]\)。选定一些物品，在 \(\sum w[i]\leq n\) 的前提下，\(\sum v[i]\times w[i]\) 最大。
这本质上是一个 0-1 背包问题。每个物品质量为 \(v[i]\)，价值为 \(v[i]\times w[i]\)。
于是设 \(f[i,j]\) 为考虑到第 \(i\) 个物品时，花费 \(j\) 元所得最大值。于是
\[f[i, j]=max(f[i,j],f[i-v[i]]+v[i]\times w[i])
\]
然后可以利用滚动数组优化，注意别滚反了。
P1802 5 倍经验日
\[\]
\[\]
\[\]
\[\]
\[\]