每日5题–0710

今天说一些DP(Dynamic Programming)的题目

我对DP的理解, 如果一个问题可以从optimal substructure推出, 那么就可以考虑用DP做, DP的优点, 比较简单直接好理解,

最难的部分应该是找到那个递推表达式.

1. LCS(longest common sequence)
给出数组 a[M], b[N], 找出, 他们之间最长的common sequence, 比如
a = “apple is fashion”
b = “google is not evil”

那么得到的输出结果就是

The LCS number is 7
“le is n”

可见这两句看上去没有什么关系的话还是有一定联系的, lol

如果定义 F(i, j) 是a[0]….a[i], 和 b[0]…b[j]之间的common sequence 的个数

所以

$F(i,j) =\left\{\begin{matrix}F(i-1, j-1)+1&if\quad a[i] = b[j] \\max\{F(i-1, j), F(i, j-1)\}&if\quad a[i] !=b[j]\\\end{matrix}\right.$

如果两个数组的长度分别是LEN1, LEN2, 那么时间复杂度是O(LEN1*LEN2), 然后还需要O(LEN1*LEN2)的空间复杂度.

2. 操作次数问题(operation)

如果有两个字符串str1, str2, 怎么用最少的操作让str1 变成 str2

你可以利用的操作有 1. 插入(insert) 2. 替换(replace) 3. 删除(delete)

再次开动脑经, 如果记录 F(i, j) 为str1[0…i]变成str2[0….j]所需要的操作的数目.

那么就有

$F(i,j) =\left\{\begin{matrix}F(i-1, j-1)&if\quad str1[i] = str2[j] \\min\left\{\begin{matrix}F(i-1, j) (deletion)\\ F(i, j-1) (insertion)\\F(i-1,j-1) (replace)\\\end{matrix}\right.+1&if\quad str1[i] !=str2[j]\\\end{matrix}\right.$

时间复杂度是 O(LEN1*LEN2)

每日5题–0710

One thought on “每日5题–0710”

Leave a Reply