算法学习——子序列性质相关经典算法

Longest Common Subsequence（LCS，最长公共子序列）

• DP算法
• 状态f[i][j]: 字符串A前i个字符和字符串B前j个字符的LCS
• 转移方程：
  if A[i-1] != B[j-1],
  
  $$f[i][j]=max \{ f[i-1][j], f[i][j-1], f[i-1][j-1] \}$$
  if A[i-1] == B[j-1],
  
  $$f[i][j]=max \{ f[i-1][j], f[i][j-1], f[i-1][j-1]+1 \}$$
• Code:

int longestCommonSubsequence(string &A, string &B) {
        // case 1
        if(A.empty() || B.empty()) return 0;

        // case 2
        int n = A.size(), m = B.size();
        // init null has 0 common subsequence with others
        vector<vector<int>> f(n+1, vector<int>(m+1, 0));

        for(int i=1; i<=n; ++i){
            for(int j=1; j<=m; ++j){
                if(A[i-1] == B[j-1])
                    f[i][j] = max(max(f[i-1][j], f[i][j-1]), f[i-1][j-1]+1);
                else{
                    f[i][j] = max(max(f[i-1][j], f[i][j-1]), f[i-1][j-1]);
                }
            }
        }

        return f[n][m];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Longest Palindromic Subsequence(最长回文子序列)

Longest Increasing Continuous Subsequence(最长连续上升子序列)

Longest Increasing Subsequence(最长上升子序列)