42_动态规划实战

文章目录
  1. 1. 量化两个字符串的相似度
  2. 2. 如何计算

记录动态规划思想

量化两个字符串的相似度

  1. 莱文斯坦距离
  2. 最长公共子串

如何计算

  1. 一个字符一个字符的比较,符合段阶段最优解
  2. 回溯(暴力破解)

相等: 如果a[i]和 b[i] 匹配 ,我们递归的考察a[i+1] b[j+1]
如果不匹配:

  • 可以删除a[i] 比较a[i+1] ,b[j]
  • 可以删除b[j] 比较a[i],b[j+1]
  • 可以在a[i] 前面添加一个和b[j] 相等的字符,比较a[i],b[j+1]
  • 可以在b[j] 前面添加一个a[i] 想的的字符,比较a[i+1] b[j]
  • 可以将a[i] 替换成b[j] 或者b[j] 替换a[i] 然后递归的考察a[i+1] b[j+1]
  1. 递归树,查看是否有重复的问题
  2. 状态转移公式
  3. 状态表
  4. 代码填状态表 (一定考虑前一个状态到当前状态转化的方式)

下面是莱文斯坦距离的两种计算方式,回缩法、动态规划:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class StringDistance {
let a = "mitcmu"
let b = "mtacnu"
let n = 6
let m = 6
var minDis = Int.max
func lwstBT(i: Int, j:Int , edist: Int) {
if i == n || j == m {
var minEditDidtance = edist

if i < n {
minEditDidtance += (n - i)
}
if j < m {
minEditDidtance += (m-j)
}
if minEditDidtance < minDis {
minDis = minEditDidtance
}
return
}
if a[a.ljIndex(i)] == b[b.ljIndex(j)] {
lwstBT(i: i + 1, j: j+1, edist: edist)
} else { //两个字符不匹配
lwstBT(i: i, j: j+1, edist: edist + 1) // 删除 b[j] 或者 a[i] 前添加一个字符
lwstBT(i: i+1, j: j, edist: edist + 1) // 删除 a[i] 或者 b[j] 前添加一个字符
lwstBT(i: i+1, j: j+1, edist: edist + 1) // 将 a[i] 和 b[j] 替换为相同字符
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func lwstDP() -> Int {
//初始化状态表
var status = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)

//初始状态
for j in 0..<m { // 初始化第 0 行:a[0..0] 与 b[0..j] 的编辑距离
if a[a.ljIndex(0)] == b[b.ljIndex(j)] {
status[0][j] = j
} else if j != 0 {
status[0][j] = status[0][j-1]+1
} else {
status[0][j] = 1
}
}

for i in 0..<n { // 初始化第 0 列:a[0..i] 与 b[0..0] 的编辑距离
if a[a.ljIndex(i)] == b[b.ljIndex(0)] {
status[i][0] = i
} else if i != 0 {
status[i][0] = status[i-1][0]+1
} else {
status[i][0] = 1
}
}

for i in 1..<n { // 按行填表
for j in 1..<m {
if a[a.ljIndex(i)] == b[b.ljIndex(j)] {
status[i][j] = min(status[i-1][j],status[i][j-1],status[i-1][j-1])
} else {
status[i][j] = min(status[i-1][j],status[i][j-1],status[i-1][j-1]) + 1
}
}
}
return status[n-1][m-1]
}

下面是最长公共子串的动态规划代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func lcs() -> Int {
//初始化状态表
var status = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)

//初始状态
for j in 0..<m { // 初始化第 0 行:a[0..0] 与 b[0..j] 的编辑距离
if a[a.ljIndex(0)] == b[b.ljIndex(j)] {
status[0][j] = 1
} else if j != 0 {
status[0][j] = status[0][j-1]
} else {
status[0][j] = 0
}
}

for i in 0..<n { // 初始化第 0 列:a[0..i] 与 b[0..0] 的编辑距离
if a[a.ljIndex(i)] == b[b.ljIndex(0)] {
status[i][0] = 1
} else if i != 0 {
status[i][0] = status[i-1][0]
} else {
status[i][0] = 0
}
}

for i in 1..<n { // 按行填表
for j in 1..<m {
if a[a.ljIndex(i)] == b[b.ljIndex(j)] {
status[i][j] = max(status[i-1][j],status[i][j-1],status[i-1][j-1]+1)
} else {
status[i][j] = max(status[i-1][j],status[i][j-1],status[i-1][j-1])
}
}
}
return status[n-1][m-1]
}