线性DP简单总结
动态规划原理
可以用动态规划解决的问题，应具备三种条件：
- 最优子结构 （由小推大）
- 无后效性（由过去推现在）
- 子问题重叠（已经求解的子问题不必重复求解）
动态规划构成
“状态” “阶段” “决策” 为动态规划三要素。
最长上升子序列
问题
给定一个长度为 \(n\) 的序列 \(A\)，求出一个最长的 \(A\) 的子序列，满足该子序列的后一个元素不小于等于前一个元素。
状态表示
\(dp_i\) 表示以 \(A_i\) 为结尾的最长上升子序列的长度
转移方程
\[f_i=\max \left(f_j+1 \right) \]目标
\[\max \left(f_i \right) \]代码
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++)
if (a[i] > a[j])
dp[i] = max(dp[i], dp[j] + 1), ans = max(ans, dp[i]);
}
最长公共子序列
问题
给定一个长度为 \(n\) 的序列 \(A\) 和一个 长度为 \(m\) 的序列 \(B\)，求出一个最长的序列，使得该序列既是 \(A\) 的子序列，也是 \(B\) 的子序列
状态表示
设 \(f_{i,j}\) 表示只考虑 \(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\ne B_j\end{cases} \]目标
\[f_{n, m} \]代码
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);