【C++刷题】优选算法——动态规划第五辑

1. 最长公共子序列

状态表示:
	选取第一个字符串[0,i]区间和第二个字符串[0,j]区间作为研究对象
	dp[i][j]: 表示s1的[0,i]区间和s2的[0,j]区间内的所有子序列中，最长公共子序列的长度
状态转移方程:
	text1[i] == text2[j]:
		dp[i][j] = dp[i-1][j-1] + 1;
	text1[i] != text2[j]:
		dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
1
2
3
4
5
6
7
8

int longestCommonSubsequence(string text1, string text2)
{
    // 1.dp数组
    vector<vector<int>> dp(text1.size(), vector<int>(text2.size()));

    // 2.初始化
    if(text1[0] == text2[0]) dp[0][0] = 1;
    for(int i = 1; i < text1.size(); ++i)
    {
        if(text1[i] == text2[0]) dp[i][0] = 1;
        else dp[i][0] = dp[i-1][0];
    }
    for(int j = 1; j < text2.size(); ++j)
    {
        if(text2[j] == text1[0]) dp[0][j] = 1;
        else dp[0][j] = dp[0][j-1];
    }

    // 3.状态转移方程
    for(int i = 1; i < text1.size(); ++i)
    {
        for(int j = 1; j < text2.size(); ++j)
        {
            if(text1[i] == text2[j])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // 4.返回值
    return dp.back().back();
}
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

2. 不相交的线

状态表示 & 状态转移方程: 参考1.最长公共子序列
1

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2)
{
    // 1.dp数组
    vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size()));

    // 2.初始化
    if(nums1[0] == nums2[0]) dp[0][0] = 1;
    for(int i = 1; i < nums1.size(); ++i)
    {
        if(nums1[i] == nums2[0]) dp[i][0] = 1;
        else dp[i][0] = dp[i-1][0];
    }
    for(int j = 1; j < nums2.size(); ++j)
    {
        if(nums2[j] == nums1[0]) dp[0][j] = 1;
        else dp[0][j] = dp[0][j-1];
    }

    // 3.状态转移方程
    for(int i = 1; i < nums1.size(); ++i)
    {
        for(int j = 1; j < nums2.size(); ++j)
        {
            if(nums1[i] == nums2[j]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }

    // 4.返回值
    return dp.back().back();
}
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

3. 不同的子序列

状态表示:
	dp[i][j]: 表示 s 字符串 [0, i] 区间内的所有子序列中，有多少个 t 字符串 [0, j] 区间子串
状态转移方程:
	s[i] == t[j]: dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
	s[i] != t[j]: dp[i][j] = dp[i-1][j]
1
2
3
4
5

int numDistinct(string s, string t)
{
    // 1.dp数组
    vector<vector<unsigned int>> dp(s.size(), vector<unsigned int>(t.size()));

    // 2.初始化
    if(s[0] == t[0]) dp[0][0] = 1;
    for(int i = 1; i < s.size(); ++i)
    {
        if(s[i] == t[0]) dp[i][0] = dp[i-1][0] + 1;
        else dp[i][0] = dp[i-1][0];
    }

    // 3.状态转移方程
    for(int i = 1; i < s.size(); ++i)
    {
        for(int j = 1; j < t.size(); ++j)
        {
            if(s[i] == t[j]) dp[i][j] += dp[i-1][j-1];
            dp[i][j] += dp[i-1][j];
        }
    }

    // 4.返回值
    return dp.back().back();
}
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

4. 通配符匹配

状态表示:
	dp[i][j]: 表示字符模式p的[0,j]区间子串，能否匹配字符串s的[0,i]区间子串
状态转移方程:
	p最后一个字符是英文字符:
		dp[i][j] = p[j] == s[i] && dp[i-1][j-1]
	p最后一个字符是'?':
		dp[i][j] = dp[i-1][j-1]
	p最后一个字符是'*':
		dp[i][j] = dp[i-1][j] || dp[i][j-1]
1
2
3
4
5
6
7
8
9

bool isMatch(string s, string p)
{
    // 1.dp数组
    vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));

    // 2.初始化
    // p[0] - ""
    dp[0][0] = true;
    // s[0] = ""
    for(int j = 1; j <= p.size(); ++j)
    {
        if(p[j-1] == '*') dp[0][j] = true;            
        else break;
    }
    // 3.状态转移方程
    for(int i = 1; i <= s.size(); ++i)
    {
        for(int j = 1; j <= p.size(); ++j)
        {
            if(isalpha(p[j-1]))
            {
                if(p[j-1] == s[i-1] && dp[i-1][j-1]) dp[i][j] = true;
            }
            else if(p[j-1] == '?')
            {
                if(dp[i-1][j-1]) dp[i][j] = true;
            }
            else
            {
            	// 方式一
                dp[i][j] = dp[i-1][j] || dp[i][j-1];
                // 方式二
                // for(int k = 0; k <= i; ++k)
                // {
                //     if(dp[k][j-1])
                //     {
                //         dp[i][j] = true;
                //         break;
                //     }
                // }
            }
        }
    }
    // 4.返回值
    return dp.back().back();
}
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
37
38
39
40
41
42
43
44
45
46

5. 正则表达式匹配

状态表示:
	dp[i][j]: 表示字符规律p的[0,j]区间子串，能否匹配字符串s的[0,i]区间子串
1
2

bool isMatch(string s, string p)
{
    // 0.预处理
    s = " " + s;
    p = " " + p;

    // 1.dp数组
    vector<vector<bool>> dp(s.size(), vector<bool>(p.size(), false));

    // 2.初始化
    // p[0]
    dp[0][0] = true;
    // s[0]
    for(int j = 2; j < dp[0].size(); j += 2)
    {
        if(p[j] == '*') dp[0][j] = true;
        else break;
    }
    
    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 1; j < dp[0].size(); ++j)
        {
            if(isalpha(p[j]))
            {
                if(p[j] == s[i] && dp[i-1][j-1]) dp[i][j] = true;
            }
            else if(p[j] == '.')
            {
                if(dp[i-1][j-1]) dp[i][j] = true;
            }
            else
            {
                if(p[j-1] == '.')
                {
                    dp[i][j] = dp[i][j-2] || dp[i-1][j];
                }
                else
                {
                    dp[i][j] = dp[i][j-2] || (p[j-1] == s[i] && dp[i-1][j]);
                }
            }
        }
    }

    // 4.返回值
    return dp.back().back();
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49

6. 交错字符串

状态表示:
	dp[i][j]: 表示s1中[1,i]区间子串和s2中[1,j]区间子串能否拼凑成s3中[1,i+j]区间子串
1
2

bool isInterleave(string s1, string s2, string s3)
{
    // 0.预处理
    if(s3.size() != s1.size() + s2.size()) return false;
    s1 = " " + s1;
    s2 = " " + s2;
    s3 = " " + s3;
    
    // 1.dp数组
    vector<vector<bool>> dp(s1.size(), vector<bool>(s2.size()));

    // 2.初始化
    dp[0][0] = true;
    for(int j = 1; j < dp[0].size(); ++j)
    {
        if(s2[j] == s3[j]) dp[0][j] = true;
        else break;
    }
    for(int i = 1; i < dp.size(); ++i)
    {
        if(s1[i] == s3[i]) dp[i][0] = true;
        else break;
    }

    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 1; j < dp[0].size(); ++j)
        {
            if((s1[i] == s3[i+j] && dp[i-1][j])
            || (s2[j] == s3[i+j] && dp[i][j-1]))
                dp[i][j] = true;
        }
    }

    // 4.返回值
    return dp.back().back();
}
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
37
38

7. 两个字符串的最小ASCII删除和

问题转化:
	求两个字符串所有公共子序列的ASCII码值最大和
状态表示:
	dp[i][j]: 表示s1的[0,i]区间和s2的[0,j]区间内的所有子序列中，公共子序列的ASCII码值最大和
1
2
3
4

int minimumDeleteSum(string s1, string s2)
{
    // 0.预处理
    int sum = 0;
    for(char c : s1) sum += c;
    for(char c : s2) sum += c;
    s1 = " " + s1;
    s2 = " " + s2;

    // 1.dp数组
    vector<vector<int>> dp(s1.size(), vector<int>(s2.size()));

    // 2.初始化

    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 1; j < dp[0].size(); ++j)
        {
            if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + s1[i];
            if(dp[i-1][j] > dp[i][j]) dp[i][j] = dp[i-1][j];
            if(dp[i][j-1] > dp[i][j]) dp[i][j] = dp[i][j-1];
        }
    }

    // 4.返回值
    return sum - 2 * dp.back().back();
}
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

8. 最长重复子数组

状态表示:
	dp[i][j]: 表示num1中以i位置元素为结尾的所有子数组和num2中以j位置元素为结尾的所有子数组中，最长重复子数组的长度
1
2

int findLength(vector<int>& nums1, vector<int>& nums2)
{
    // 1.dp数组
    vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1));

    // 2.初始化

    // 3.状态转移方程
    int ret = 0;
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 1; j < dp[0].size(); ++j)
        {
            if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            ret = max(ret, dp[i][j]);
        } 
    }

    // 4.返回值
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21