数据结构和算法 -- 子序列问题

一、子序列问题

        子数组问题是连续的，而子序列问题是不连续的。比如说字符串 “I wanna keep a giraffe in my backyard” 的一种子序列就可以是 “Igbackd”。 子序列不再要求答案是一个连续的串。一个字符串的子序列，是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。举个例子，“ace” 是 “abcde” 的子序列，但是 “aec” 就不是 “abcde” 的子序列。

二、最长回文子序列

1、问题描述

问题：给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000。 

1.  
    
2.  
   示例1：
3.  
    
4.  
   输入："asssasms"
5.  
   输出：5
6.  
   解释：一个可能的最长回文子序列为 "sssss"，另一种可能的答案是 "asssa"。

2、算法分析

1）初始化状态

        单个字符一定是它自己的回文；

2）状态参数

        一个是起始位置，另一个是结束位置。在算法的执行过程中，起始和结束位置是变化的，因此它们是状态参数。 

3）决策

        当前子问题的答案就是通过前面的子问题 ➕ 当前的决策推导出来的。当前的决策就是：计算出向子问题的两边分别扩充一个元素后得到的答案。 

4）备忘录

        DP[i][j]，其对应的值是字符串 i…j 中最长回文子序列的长度。 

3、状态方程

4、算法实现

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
    
6.  
   func DP(str string, length int) int {
7.  
   byteSlice := []byte(str)
8.  
    
9.  
   // 创建备忘录
10.  
    dp := make([][]int, length)
11.  
    for i := range dp{
12.  
    dp[i] = make([]int, length)
13.  
    }
14.  
     
15.  
    // 初始化状态
16.  
    for i := 0; i < length; i {
17.  
    dp[i][i] = 1
18.  
    }
19.  
     
20.  
    // 转移方程转换实现
21.  
    for i := length - 1; i >= 0; i-- {
22.  
    for j := i 1; j < length; j {
23.  
    if byteSlice[i] == byteSlice[j] {
24.  
    dp[i][j] = 2 dp[i 1][j-1];
25.  
    } else {
26.  
    if dp[i 1][j] > dp[i][j-1] {
27.  
    dp[i][j] = dp[i 1][j]
28.  
    } else {
29.  
    dp[i][j] = dp[i][j-1]
30.  
    }
31.  
    }
32.  
    }
33.  
    }
34.  
    return dp[0][length-1] // 输出答案
35.  
    }
36.  
     
37.  
    func main() {
38.  
    str := "asssasms"
39.  
    length := len(str)
40.  
    fmt.Println(DP(str, length)) // 输出答案
41.  
    }

三、最长公共子序列

1、问题描述

问题：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。若这两个字符串没有公共子序列，则返回 0。

其中：

1 ≤ text1.length ≤ 1000；

1 ≤ text2.length ≤ 1000；

输入的字符串只含有小写英文字符。 

1.  
    
2.  
   示例1：
3.  
    
4.  
   输入：text1 = "abcde", text2 = "ade"
5.  
   输出：3
6.  
   解释：最长公共子序列是 "ade"，它的长度为 3。

2、算法分析

1）初始化状态

        当两个字符的其中一个为空串，或同时为空串时，原问题的答案肯定是 0。显然，一个字符串与空串的公共子序列肯定是空的。 

2）状态参数

        用变量 i 和变量 j 描述了整个问题的求解空间，备忘录是基于二维数组构建的。因此，我们的状态参数就是变量 i 和变量 j。 

3）决策

对于 text1 和 text2 这两个字符串中的每个字符 text1[i] 和 text2[j]，其实只有两种选择：

1、text1[i−1]==text2[j−1]，即当前遍历的两个字符在最长公共子序列中，此时 DP[i][j]=1 DP[i−1][j−1]；

2、text1[i−1]!=text2[j−1]，即当前遍历的两个字符至少有一个不在最长公共子序列中。仿照最长回文子序列的处理方法，由于两个字符至少有一个不在，因此我们需要丢弃一个。因此在不等的情况下，需要进一步作出决策。 

由于我们要求的是最长公共子序列，因此哪个子问题的答案比较长，就留下谁：max(DP[i−1][j], DP[i][j−1])。

4）备忘录

        DP[i][j] 表示的是 text1[0…i] 和 text2[0…j] 的最长公共子序列的长度。 

3、状态方程

4、算法实现

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
    
6.  
   func DP(str1 string, str2 string) int {
7.  
   byteSlice1 := []byte(str1)
8.  
   byteSlice2 := []byte(str2)
9.  
    
10.  
    length1 := len(str1)
11.  
    length2 := len(str2)
12.  
     
13.  
    // 创建备忘录
14.  
    dp := make([][]int, length1 1)
15.  
    for i := range dp{
16.  
    dp[i] = make([]int, length2 1)
17.  
    }
18.  
     
19.  
    // 初始化状态
20.  
    for i := 0; i < length1 1; i {
21.  
    for j := 0; j < length2 1; j {
22.  
    dp[i][j] = 0
23.  
    }
24.  
    }
25.  
     
26.  
    // 转移方程转换实现
27.  
    for i := 1; i<= length1; i {
28.  
    for j := 1; j <= length2; j {
29.  
    if byteSlice1[i-1] == byteSlice2[j-1] {
30.  
    dp[i][j] = 1 dp[i-1][j-1];
31.  
    } else {
32.  
    if dp[i-1][j] > dp[i][j-1] {
33.  
    dp[i][j] = dp[i-1][j]
34.  
    } else {
35.  
    dp[i][j] = dp[i][j-1]
36.  
    }
37.  
    }
38.  
    }
39.  
    }
40.  
    return dp[length1][length2] // 输出答案
41.  
    }
42.  
     
43.  
    func main() {
44.  
    str1 := "abcde"
45.  
    str2 := "ade"
46.  
    fmt.Println(DP(str1, str2)) // 输出答案
47.  
    }

声明：本文参考极客时间《动态规划面试宝典》 

这篇好文章是转载于：学新通技术网