ch6 递推与动态规划¶
1. 递推¶
递推流程：
设定递推初值。
依公式递推，常用循环实现。
递推优点：
递推公式往往比通项公式容易得到。
计算机非常擅长递推公式的重复计算。
2. 动态规划¶
把问题分解为多个阶段：
每个阶段面临的都是与原问题相似的子问题。
子问题的最优解能够累积得到整体最优解，或者说整体最优解的每个阶段都是子问题的最优解（最优性原理）。
找出每个阶段下的多个状态：
考虑每个状态下有哪些可选的决策。
找出每个状态下的最优决策。
写出最优决策下状态转移的递推公式。
考虑递推的方向，并由此确定递推初始值。
考虑如何记录最优决策，以便输出整体最优解。
3. 最长公共子序列¶
把问题分解为多个阶段：
逐个字母依次比较，是自然的阶段划分。
每个阶段面临的都是与原问题相似的子问题：
显然，子问题是 “求缩短后序列的最长公共子序列”。
最优性原理：
如果首字母相同，我们的策略能够保证累积得到一个整体最优解。如果首字母不同，不会丢失整体最优解。
找出每个阶段下的多个状态：
只有 \(1\) 个状态：求 \(\tt A[i,m)\) 与 \(\tt B[j,n)\) 的最长公共子序列。
考虑每个状态下有哪些可选的决策：
我们只考虑了一种 “不会亏” 的决策。
找出每个状态下的最优决策：
“不会亏” 的决策是一种最优决策。
当 \(\tt A[i]=B[j]\) 时，\(\tt A[i](B[j])\) 加入公共子序列；
当 \(\tt A[i]\ne B[j]\) 时，抛弃 \(\tt B[j]\) 或 \(\tt A[i]\)，取两者中较优的。
写出最优决策下状态转移的递推公式：
\(\tt lcs(i,j) =
\begin{cases}
\tt 1 + lcs(i+1, j+1), & \tt if(A[i] = B[j]) \\
\tt max\{lcs(i, j+1), lcs(i+1, j)\}, & \tt if (A[i] \ne B[j])
\end{cases}\)
考虑递推的方向，并由此确定递推初始值。
计算 \(\tt lcs[i,j]\) 需要 \(\tt lcs[i+1,j+1],\ lcs[i+1,j],\ lcs[i,j+1]\)，因此递推从较大的下标开始逆推。于是递推初值为 \(\tt lcs\) 数组的第 \(n\) 行和第 \(m\) 列的值为 \(0\)。