线性动态规划

数字三角形问题

例题：数字三角形

本题DP数组及数字三角形的下标最好从1开始。

数字三角形动态规划问题：

• 状态表示： \(f(i,j)\)：
  • 集合：所有从起点走到点 \((i,j)\) 的路径；
  • 属性：集合中所有路径对应的数字之和的最大值。
• 状态计算：将集合 \(f(i,j)\) 分为两类：
  • 来自左上方的路径： \(f(i-1,j-1)+a[i][j]\)；
  • 来自右上方的路径： \(f(i-1,j)+a[i][j]\)。

动态规划问题是时间复杂度一般为“状态数量”乘以“每个状态转移需要的计算量”，本题时间复杂度为 \(O(n^2)\)。

最长上升子序列问题

例题：最长上升子序列；保存最长上升子序列

最长上升子序列动态规划问题：

• 状态表示： \(f[i]\)：
  • 集合：所有以第 \(i\) 个数为结尾的数值上升子序列的集合；
  • 属性：集合每个上升子序列的长度的最大值。
• 状态计算：按倒数第二个数是哪个来划分集合，要么序列里只有一个数( \(0\) )，要么倒数第二个数的下标可能为 \(1,2,\cdots ,n-1\)，这些类不一定都存在。

对于最后两个数分别为 \(a_j,a_i\) 的上升子序列( \(a_j < a_i\) )，满足其长度为 \(f[j]+1\)，则 \(f[i]=\max (f[j]+1), a_j < a_i;\ j=0,1,\cdots ,i-1\)。

时间复杂度为 \(O(n^2)\)。

例题：最长上升子序列2

当数据范围较大时，应该寻找一种时间复杂度更低的方式。

扩展解法可把时间复杂度降到 \(O(n\log n)\)。

最长公共子序列问题

例题：最长公共子序列

最长公共子序列(不是字串)动态规划问题：

• 状态表示： \(f(i,j)\)：
  • 集合：所有由第一个序列的前 \(i\) 个字母和第二个序列的前 \(j\) 个字母构成的公共子序列，也就是所有在第一个序列的前 \(i\) 个字母中出现，且在第二个序列的前 \(j\) 个字母中出现的子序列；
  • 属性：所有这些子序列长度的最大值。
• 状态计算：以a[i]、b[j]是否包含在子序列中来划分集合(共四种情况)：
  • “情况 \(00\) ” (不选a[i]，不选b[j])： \(f(i-1,j-1)\)，一般代码中可以不写这种情况，因为 \(f(i-1,j)\) 和 \(f(i,j-1)\) 已经包含了这种情形；
  • “情况 \(01\) ” (不选a[i]，选b[j])：注意 \(f(i-1,j)\) 不一定包含b[j](即“情况 \(01\) ”为 \(f(i-1,j)\) 的子集，而不是相等)，但为了求最大值，可以用 \(f(i-1,j)\) 来替换，即使集合划分出现重复也没事(因为求的是最大值，只要不漏掉元素就行)；
  • “情况 \(10\) ” (选a[i]，不选b[j])：为了求最大值，可以用 \(f(i,j-1)\) 来替换；
  • “情况 \(11\) ” (选a[i]，选b[j])： \(f(i-1,j-1)+1\)。

时间复杂度为 \(O(n^2)\)。

注：以上第二种情况(“情况 \(01\) ”)指的是a[i]不出现在子序列中，b[j]一定出现在子序列中， \(f(i-1,j)\) 严格包含这种情况。为什么？

第二种状态(“情况 \(01\) ”)的意思是：a[i]一定不在子序列中，且最后一个字母一定是b[j]；而 \(f(i-1,j)\) 的意思是，a的前i - 1和b的前j中出现公共子序列，所以是第二种状态的条件更强。

• 为什么有重复？因为第二种状态更强， \(f(i-1,j)\) 条件弱一点，所以用 \(f(i-1,j)\) 表示第二种状态里面肯定会有重复的；
• 为什么求最大值可以重复？如果取最大值的话，重复也就无所谓了，就算重复最大值依然是最大值。

编辑距离问题

例题：最短编辑距离

该问题可进行如下分析：

• 状态表示：
• 集合：所有将a[1~i]变为b[1~j]的操作方式；
• 属性：所有操作方式的操作次数的最小值。
• 状态计算：f[i,j]，按如下方式划分集合：
• 最后一步 删除 a[i]：f[i - 1, j] + 1；
• 最后一步 增加 a[i] == b[j]：f[i, j - 1] + 1；
• 最后一步 修改 a[i]：根据a[i]与b[j]是否相等来分类讨论，f[i - 1, j - 1] + 1或0。

f[i, j]为以上三种情况的最小值，时间复杂度为 \(O(n^2)\)。

例题：编辑距离