# 动态规划

1. 动态规划时用来解决优化问题，可以输出*一个*最优解 (可能有多个最优解)

2. 切钢管
   - 问题描述：给定长 $n$ 米的钢管，和一个价格表 $p_i$ 对应 $i=1,2,\ldots,n$，求如何使得收益最大
   - 如果暴力搜索，则为指数复杂度 $O(2^n)$
   - 递推式 $r_n=\max_{1\leqslant i\leqslant n}(p_i+r_{n-i})$
   - 时间复杂度为 $O(n^2)$

3. 矩阵链乘
   - 问题描述：给定 $n$ 个矩阵 $A_1,A_2,\ldots,A_n$，求如何加括号使得乘法次数最少？每个矩阵的维度为 $p_{i-1}\times p_i$
   - 递推式 $$m[i,j]=\begin{cases}0,&i=j\\min_{i\leqslant k<j}(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j),&i<j\end{cases}$$
   - 时间复杂度为 $O(n^3)$

4. 一个优化问题必须有两条关键性质才能使用动态规划
   - 最优子结构：原问题的解可以由多个子问题的最优解组合而成
   - 子问题重叠：子问题间需要有重叠，否则动态规划不会比朴素算法更快

5. 动态规划本质是空间换时间

6. 最长公共子序列问题
   - 定义子序列：给定一条序列 $X=<x_1,x_2,\ldots,x_m>$，则序列 $Z=<z_1,z_2,\ldots,z_k>$ 为 $X$ 的子序列，当存在一个严格递增的序列 $<i_1,i_2,\ldots,i_k>$ 使得对于所有 $j=1,2,\ldots,k$ 有 $x_{i_j}=z_j$.
   - 公共子序列，即一个序列同时是两个序列的子序列
   - 以下称 $X_i=<x_1,x_2,\ldots,x_i>$ 为 $X=<x_1,x_2,\ldots,x_m>$ 的第 $i$ 个前缀，$i=0,1,\ldots,m$
   - 给出定理：$X=<x_1,x_2,\ldots,x_m>,Y=<y_1,y_2,\ldots,y_n>$ 的最长公共子序列为 $Z=<z_1,z_2,\ldots,z_k>$
     - 若 $x_m=y_n$ 则 $z_k=x_m=y_n$，$Z_{k-1}$ 为 $X_{m-1}$ 和 $Y_{n-1}$ 的最长公共子序列
     - 如果 $x_m\neq y_n$ 则 $z_k\neq x_m$ 意味着 $Z$ 是 $X_{m-1}$ 和 $Y$ 的最长公共子序列
     - 如果 $x_m\neq y_n$ 则 $z_k\neq y_n$ 意味着 $Z$ 是 $X$ 和 $Y_{n-1}$ 的最长公共子序列
   - 则有如下递推式 $$c[i,j]=\begin{cases}0,&i=0\ {\rm or}\ j=0\\c[i-1,j-1]+1,&i,j>0\ {\rm and}\ x_i=y_j\\max(c[i,j-1],c[i-1,j]),&i,j>0\ {\rm and}\ x_i\neq y_j\end{cases}$$
   - 时间和空间复杂度都为 $O(mn)$

7. 最优二叉搜索树
   - 问题描述：已知有 $n$ 个互不相同且递增的键值 $k_1,k_2,\ldots,k_n$，搜索到 $k_i$ 的概率为 $p_i$；同时有 $d_0,d_1,\ldots,d_n$ 代表在 $k_i$ 之间的值，搜索到 $d_i$ 的概率为 $q_i$，有约束 $\sum p_i+\sum q_i=1$，求最小化二叉搜索树的期望搜索代价 $E=\sum_{i=1}^n(d(k_i)+1)p_i+\sum_{i=0}^n(d(d_i)+1)q_i$
   - 有如下递归式 $$e[i,j]=\begin{cases}q_{i-1},&j=i-1\\\min_{i\leqslant r\leqslant j}(e[i,r-1]+e[r+1,j]+w(i,j)),&i\leqslant j\end{cases}$$
   - 时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$
