Skip to content旅行商问题（TSP）
给定 \(n\) 个城市 \(V = {0, 1, 2, \dots, n-1}\)，两两城市间距离 \(\text{dist}[i] [j]\)。旅行商必须从某个城市出发，访问每个城市恰好一次，最后回到起点。希望使总路程最短，即 \(\text{dist}[\pi_0][\pi_1] + \text{dist}[\pi_1][\pi_2] + \cdots + \text{dist}[\pi_{n-1}][\pi_0]\) 最小，其中 \(\pi_i\) 表示第 i 个经过的城市。
令 \(dp[S] [i]\) 表示从起点 0 出发，访问完集合 \(S\) 中的所有城市（包含 0 和 i），并以城市 \(i\) 结尾的最短路径长度。
初始化：\(dp[{0}][0] = 0\)
状态转移：若我们当前到达城市 \( i\)，上一步一定来自 \(S\setminus{i}\) 的某个城市 \(j\)。故：
\[dp[S][i] = \min_{j \in S, j \ne i} (dp[S \setminus {i}][j] + dist[j][i])\]TSP 的时间复杂度：
对于集合 \(S\) 的每个子集 \(S_k\)，你可能以集合中的任意一个城市结尾。因此状态数 \(m\) 等于大小为 \(k\) 的集合个数乘 \(k\) 再求和。
\[m = \sum_{k=1}^{n} \binom{n}{k} \cdot k= n \cdot 2^{n-1}= O(n \cdot 2^n)\]对于每个状态 \(dp[S] [i]\)，要考虑从哪个城市 \(j\) 转移过来。内层要枚举所有 \(j\in S\setminus{i}\)，最多有 \(n\) 个候选城市。因此每个状态的转移代价 = \(O(n)\)。
总时间复杂度等于状态数乘每个状态的转移代价。
\[TC= O(m \times \text{cost per state})= O(n^2 2^n)\]最长公共子序列
给定两个序列（如两个字符串）A 与 B，最长公共子序列是同时作为两者子序列（不一定连续）的序列中长度最大的那个，求长度。
令 \(dp[i] [j]\) 表示取 A 字符串前 \(i\) 个字符、B 字符串前 \(j\) 个字符时，最长公共子序列的长度。
状态转移：
\[
dp[i][j]=\begin{cases}
dp[i-1][j-1]+1, & A[i-1]==B[i-1] \\
\max(dp[i-1][j],\, dp[i][j-1]), & A[i-1]\neq B[i-1]
\end{cases}
\]Weighted interval scheduling
给定 n 门课的起始时间和权重 \(w_i\)，要求排课不冲突且权重之和最大。
\(dp[i]\) 表示前 i 门课中最优的排课方式，\(p(i)\) 表示结束时间最晚的和第 i 节课不冲突的课。
\[dp[i]=\max(dp[i-1],w_i+dp[p(i)])\]最大子段和
给定数组 \(A\)，找到区间使区间中数字之和最大。
\(dp[i]\) 表示以 \(A[i]\) 结尾的所有子数组中数字之和的最大值。
\[dp[i]=\max(A[i], A[i]+dp[i-1])\]如果求和时允许删掉 0 或 1 个数？
最大子矩阵和？
Segemented least squares
给定平面上 n 个点，用若干直线拟合，使直线数量尽可能少、误差尽可能小。
惩罚函数 \(f(x)=E+cL\)，其中 \(E\) 为误差之和，\(L\) 为直线数量，\(c\) 为常数。希望最小化惩罚函数。
\(dp[i]\) 表示前 i 个点的最优解。
\[dp[i]=\max_{1\le j\le i}(e_{ji}+c+dp[j-1])\]01 背包
\(dp[i][w]\) 表示前 i 个物品，背包容量为 w 时最优解。
\[dp[i][w]=\max(dp[i-1][w], v_i+dp[i-1][w-w_i])\]All-pairs shortest paths
Product assembly
最长上升子序列
\[
dp[i]=\begin{cases}
dp[i-1]+1, &A[i-1]\le A[i] \\
\end{cases}
\]Erdos-Szekeres
给定数列 \(a_1, a_2\cdots a_{n^2+1}\)，则必定存在长度为 \(n+1\) 的单调序列。
String similarity
mismatch：对应的字符不同
gap：字符和空格对应
cost：mismatch + gap
给定两个字符串，找到所有的加空格方式下 cost 的最小值。
\(dp[i][j]\) 表示字符串 1 的前 i 位、字符串 2 的前 j 位的最小 cost。
\[
dp[i][j]=\min\begin{cases}
\alpha_{x_i y_j}+dp[i-1][j-1], &\text{$x_i$ and $y_i$ matches}\\
\delta + dp[i-1][j], &\text{$x_i$ unmatched} \\
\delta + dp[i][j-1], &\text{$y_i$ unmatched}
\end{cases}
\]Hirschberg
空间复杂度 \(O(m+n)\)。