1.动态规划问题概述

基本概念

最优性原理：某些问题的最优决策序列满足如下性质，即无论过程的初始状态和初始决策是什么，其余的决策必须相对于初始决策所产生的状态构成一个最优决策序列。
最优子结构(optimal substructure)性质：和最优性原理等价，一个问题具有最优子结构性质等价于问题的最优解包含了或者说由子问题的最优解组成，并且这些子问题可以独立求解。

动态规划解决问题一般步骤

  1. 寻找问题的最优子结构性质，即找到某个问题并假设已知其最优解，满足任意子问题一定是最优的
  2. 递归定义最优解求解方案，写出最优解递归定义函数
  3. 计算最优解的值，一般是自底向上的，也可以是带备忘录的自上而下的
  4. 根据求解最优代价时记录的信息重构解，可以是递归的重构

2.钢条切割问题

问题描述

钢条切割问题给出允许得到的钢条长度i，以及对应售价$p[i]$，给定钢条总长度n，需要求解如何切割这根长n的钢条才能使得销售价格$r_n$最高？

最优子结构

反证法：
对于钢条切割问题(长度为n)，如果已知最优切割方案，那么其中任意长k的部分必然是长度为k时的最优切割方案，否则可以用更优的方案替代长k部分的现有方案，使得总体方案更优，与当前方案最优矛盾。

最优解递归定义

比较容易想到的定义方法为使用更短钢条最优解的组合进行递归描述，即所有一刀切割方案的最优解之和以及不切割方案中的最大值：
$r_n = max{p_n,r_1+r_{n-1},…,r_{n-1}+r_1}$，其中$r_k$表示长k钢条的最大收益
上述定义说明钢条切割问题满足最优子结构

简化的递归定义考虑到两个子问题相加和另外两个子问题相加实际上重复考虑了一部分可能的情况，例如$r_1+r_{n-1}$和$r_2+r_{n-2}$，都包含了$r_1+r_1+r_{n-2}$这种情况，也可以列举一下$r_1,r_2,r_3$所有可能情况，也会发现有一定的重叠。
故可以使用简化的递归定义为：
$r_n = max {p_i + r_{n-i}}$

3.矩阵链乘问题

3.1.问题描述

3.2.最优子结构

3.3.自下而上算法

4.最长公共子序列问题

4.1.问题基本定义

两个序列$X = <X_1,X_2,…,X_n>$、$Y = <Y_1,Y_2,…,Y_n>$的最长公共子序列$LCS = <A_1,…,A_k>$满足如下性质：

  1. $A_i \in X \cap Y$，即$LCS = <A_1,…,A_k> = <X_{i_1},…,X_{i_k}>$，对$Y$同理
  2. $i_1\lt … \lt i_k$，对$Y$同理
  3. 没有满足1、2中要求且比LCS更长的序列，但是可以有相同长度的其他序列

通俗的来讲，LCS指出现在X、Y中可以不连续的最长公共序列。

4.2.问题最优子结构

4.2.1.Brute-Force

问题：为什么要使用dp而不用Brute-Force？
列出一个序列A的所有子序列(subsequence)，相当于求一个大小为A中元素个数的集合的所有子集，个数为$2^{\vert A\vert}$，显然要遍历所有子序列时间复杂度至少是指数级别的。

4.2.2.最优子结构

对于一个序列$X = <x_1,…,x_m>$，定义X的第i个前缀为$X_i = <x_1,…,x_i>$。
假设需要求出X和Y的$LCS = Z = <z_i,…,z_k>$，那么根据最后一位情况的不同有以下事实：

  1. 如果$x_m = y_n$，那么必然有$x_m = y_n = z_k$，且$LCS(X_{m-1},Y_{n-1}) = Z_{k-1}$
  2. 如果$x_m \neq y_n$且$x_m \neq z_k$，那么$LCS(X_{m-1},Y_{n}) = Z$
  3. 如果$x_m \neq y_n$且$y_n \neq z_k$，那么$LCS(X_{m},Y_{n-1}) = Z$

上述事实是如何帮助找到最优子结构的？上述事实说明最后一项相等时，当前问题由一个子问题组成，即求$LCS(X_{m-1},Y_{n-1})$；不相等时，当前问题由两个子问题组成，即求$LCS(X_{m-1},Y_{n})$和$LCS(X_{m},Y_{n-1})$中更大的(因为只可能等于这两个值)。因此上述事实说明最优解是由子问题最优解构成的，因此是最优子结构性质！

证明：
对于1中结论，假设$LCS(X_{m-1},Y_{n-1}) = Z^{‘}$且比$Z$长，那么$<Z,x_m(y_n)>$是$X,Y$更长的一个公共子序列，与$Z$是LCS矛盾。
对于2,3中结论，由于是对称的，只证2。假设$LCS(X_{m-1},Y_{n}) = Z^{‘}$且比$Z$长，那么$LCS(X,Y)$长度必然大于等于$Z^{‘}$长度，也必然大于等于$Z$长度，与$Z$是LCS矛盾。

注意：2.3中逆命题不一定成立。因为即使$LCS(X_{m-1},Y_{n}) = Z$，$x_m$依然可以与$z_k$相等（当然也可以不相等），这不会影响最长子序列。因此不会出现这样的顾虑：会不会选择了$LCS(X_{m-1},Y_{n})$和$LCS(X_{m},Y_{n-1})$中更大的，导致$x_m$或$y_n$不满足2.3.中的要求？不会的原因是逆命题不成立，选哪个都不会影响$x_m$或$y_n$与$z_k$的关系。

4.3.递归定义解

令$c[i,j]$为$X_i,Y_j$的LCS的长度，那么其满足： \(c[i,j]=\begin{cases} 0 & i=0\ or\ j=0 \\ c[i-1,j-1]+1 & i,j\gt 0,x_i = y_j(=z_k) \\ max(c[i-1,j],c[i,j-1]) & i,j\gt 0, x_i \neq y_j \end{cases}\)

4.4.写出自下而上算法

4.5.重构解

扩展

问题：如何求三个序列的LCS？ 扩展4.2.2中定理。扩展后原来所谓的二维矩阵图实际上变成了三维矩阵图，也即立方体图。重构解此时在小立方体之间行进即可。
假设三个序列为$X_i,Y_j,Z_k$，LCS为$A_s$，扩展后递归定义为：
\(c[i,j,k]=\begin{cases} 0 & i=0\ or\ j=0\ or k=0 \\ c[i-1,j-1,k-1]+1 & i,j,k\gt 0,x_i = y_j = z_k(=a_s) \\ max(c[i-1,j-1,k],c[i,j,k-1]) & i,j,k\gt 0, x_i = y_j \neq z_k\\ max(c[i-1,j,k-1],c[i,j-1,k]) & i,j,k\gt 0, x_i = z_k \neq y_j\\ max(c[i,j-1,k-1],c[i-1,j,k]) & i,j,k\gt 0, y_j = z_k \neq x_i\\ max(c[i-1,j,k],c[i,j-1,k],c[i,j,k-1]) & i,j,k\gt 0, x_i \neq y_j \neq z_k \end{cases}\)

对于更多的序列同时求LCS，增加递归定义的情况即可。