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\)。
-