LCS & Dynamic programming

一周之前看到 Leetcode 每日一题最长公共子序列，没想到就解决办法就暂时搁置。第二天早上突然想到了解决办法，然而等到现在才去实现，但没有通过第 18 个单元测试，不得其解。原以为只是一个字符串问题，没想到是动态规划问题，解决还及其简洁。随后看到 6.006 后部分的动态规划时候，恰好有个相同例题，遂记录一下。

最开始思路是双重循环，记录两个字符串 x & y 中首个相同字符的位置 i，然后对剩余位置继续查找。因为还存在更好的结果，所以以 x.substring(i + 1) 进行 LCS，并返回最大值。重复至 substring 小于最长子序列。本以为已经完全 OK， 却无法通过第 18 个单元测试。没有发现错误核心，看了下评论区才知道是 DP 问题 。去油管看了解题思路，随后没想到的是 6.006 第二个例子也是 LCS，思路特别清晰，要是看完再去解就轻松多了。以 LCS 为例，记一下一般 DP 的思路。

DP = recurrence + memorize + guess

6.006 - 5 easy steps to dynamic programming:

  1. define subproblems. prefix x[:i], suffix x[i:], substring x[i:j]
  2. guess
  3. relate subproblem solutions
  4. recurse + memorize or build DP table bottom-up
  5. solve original problem

LCS 解决方法

  1. 子问题为解决子串 x[i:] & y[j:]
  2. 如果两字符串首字符相等 c(i+1, j+1)。否则猜测 x[i] 是否存在与最长子序列，如果存在：c(i, j+1)，如果不存在 c(i+1, j)
  3. recurrence
if (x[i] == y[j]) {
	c(i + 1, j + 1) + 1
	} else {
	max(c(i, j + 1), c(i + 1, j)
}

  1. topological order

    使用二位数组存储每次的结果，如果不相同取 max(c(i, j + 1), c(i + 1, j) 的值，如果相同取上一问题的值 + 1

for (int i = 1; i <= m; i++) {         
	for (int j = 1; j <= n; j++) {               
    	if (text2.charAt(j) == text1.charAt(i)) {    
    	dp[i][j] = dp[i - 1][j - 1] + 1;               
	} else {                    
		dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);         
		}
	}
}
  1. original problem: c(text1, text2)

相比最开始的思路，对于如果字符不存在的情况考虑不全面，才会未通过测试。DP 的最难点就在于 subproblem 和通过 guess 解决 subproblem。简单的 DP 基本考虑前缀后缀子串就能定义子问题，跟随步骤就可以减少很多思考。但是对于某些问题，可以更好的 guess。例如背包问题，可以通过排序解决。6.006 之后的例子也展示了需要更多 subproblem 解决更难的问题。

Contents