动态规划 - (sunznx) 振翅飞翔
14 October 2019

线性 dp

lcs 最长公共子序列:

len1 = s1.size()
len2 = s2.size()

for i = 0; i < len1; i++
  for j = 0; j < len2; j++
    if (s1[i] == s2[j])
      dp[i][j] = dp[i-1][j-1] + 1
    else
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

lis 最长上升子序列:
思路 1:对字符串 s 进行排序,设排序后的字符串为 t,计算 s 和 t 的最长公共子序列。效率 O(nlogn) + O(n2)
思路 2:设 f[i]=n 为选了 s[i] 之后, s[0..i] 最长上升子序列的长度为 n ,则 f[i] 的求法如下

for i = 0; i < len; i++
  f[i] = 1

for i = 1; i < len; i++
  for j = 0; j < i; j++
    if s[i] > s[j]
      f[i] = max(f[i], f[j]+1)

ans = f[0]
for i = 0; i < len; i++
  ans = max(ans, f[i])

最长回文子串:

# 方法1:从头推到尾
for i = 0; i < len; i++
  dp[i][i] = 1
  for j = i-1; j >= 0; j--
    if s[i] == s[j]
      dp[j][i] = dp[j+1][i-1] + 2
    else
      dp[j][i] = max(dp[j+1][i], dp[j][i-1])
return dp[0][len-1]

# 方法2:从尾推到头
for i = len-1; i >= 0; i--
  dp[i][i] = 1
  for j = i+1; j < len; j++
    if s[i] == s[j]
      dp[i][j] = dp[i+1][j-1] + 2
    else
      dp[i][j] = max(dp[i][j-1], dp[i+1][j])
return dp[0][len-1]

lics 最长公共上升子序列:
f[i][j] 表示选了 j 之后 s1[0..i]s2[0..j] 的最长公共上升子序列数目

  1. 如果 s1[i]!=s2[j]f[i][j] = f[i-1][j]
  2. 如果 s1[i]==s2[j]f[i][j] = max(f[i-1][k={0..j-1}]+1) && s2[j]>s2[k]
ans = 0
for i = 0; i < len1; i++
  for j = 0; j < len2; j++
    if s1[i] != s2[j]
      f[i][j] = f[i-1][j]
    else
      f[i][j] = 1
      for k = 0; k < j; k++
        if s1[i] > s2[k]
          f[i][j] = max(f[i][j], f[i-1][k]+1)
    ans = max(ans, f[i][j])

lics 优化:
s1[i]==s2[j] ,我们需要计算的是 s2[0~j-1] 中,比 s1[i] (或者 s2[j] ,因为 s1[i]==s2[j] )小的字符串,构成的最长公共上升子序列数目的最大值,再加 1。如果我们现在就将这个值,保存下来,设为 val ,那么在下次 s1[i+1]==s2[j] 的时候,我们只需要将 val+1 即为 f[i+1][j]

ans = 0
for i = 0; i < len1; i++
  val = 0
  for j = 0; j < len2; j++
    if s1[i] != s2[j]
      f[i][j] = f[i-1][j]
    else
      f[i][j] = val + 1

    if s1[i] > s2[j]
        val = max(val, f[i][j])
    ans = max(ans, f[i][j])

编辑距离:
设 f[i][j] 表示把 a[1..i]b[1..j] 变成相等的时候的最小花费,则

  1. 假设删除 a[i] 能使 a[1..i] 和 b[1..j] 匹配,那么 f[i][j]=f[i-1][j]+1
  2. 假设在 a[i] 后面插入一个数能使 a[1..i] 和 b[1..j] 匹配,那么 f[i][j]=f[i][j-1]+1
  3. 假设将 a[i] 修改成某一个值能使 a[1..i] 和 b[1..j] 匹配,那么需要考虑两种情况

3.1 a[i] 和 b[j] 是相等的,那么此时不需要修改了 f[i][j]=f[i-1][j-1]
3.2 a[i] 和 b[j] 是不相等,那么此时的修改开销为 1, f[i][j]=f[i-1][j-1]+1

状态压缩 dp

哈密顿回路:有 n 个顶点,从 0 开始出发,求经过所有的顶点 0~n-1 且每个点经过一次的最短路径
n 个顶点,遍历的时候则每个顶点可能出现也可能不出现,设状态为 m ,则 m 最多有 2n 种可能。例如 m=1 表示经过了顶点 0 的状态, m=3 表示经过了顶点 0 和顶点 2 的状态
f[m][i] 表示从顶点 i 到状态 m 的最短路径,则

f[0~n-1][0~n-1] = MaxValue

f[1][0] = 0

for m = 0; m < (1 << n); m++
  for i = 0; i < n; i++
    if ( (m & (1 << i)) != 0 )
      for j = 0; j < n; j++
        if i == j
          continue

        if ( (m & (1 << j)) != 0 )
          f[m][i] = max(f[m][i], f[m^(1 << i)][j] + w[i][j])