Skip to main content

双序型

David Liu4/3/26About 6 min

双序型

有两个序列/字符串，需要进行一些操作
每个序列本身是一维的，可以转化为二维动态规划

常见是匹配型，也有双区间的

两个字符串的匹配值依赖于两个字符串前缀的匹配值
字符串长度为 n,m 则需要开(n+1)x(m+1)的状态数组
要初始化dp[i][0]与dp[0][i]
通常都可以用滚动数组进行空间优化

也可以用滚动数组优化

两个一维序列/字符串

突破口

  • 串A和串B的最后一个字符是否匹配
  • 是否需要串A/串B的最后一个字符
  • 缩减问题规模

状态：f[i][j]数组下标表示序列A前i个，序列B前j个

初始条件和边界情况

  • 空串如何处理
  • 计数型（情况1+情况2+.…）以及最值型(min/max情况1，情况2，.…}》

匹配的情况下勿忘+1（操作数多1次，匹配长度多1）

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

  • For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

状态：f[i][j]表示A前i个字符A[0,i-1]和B前j个字符[0,j-1]的最长公共子串的长度

转移：f[i][j]=max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1|A[i-1]==B[j-1]}

边界：f[0][j]=0, f[i][0]=0

优化：可以滚动数组优化到On

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] f = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    return f[m][n];
}

1035. Uncrossed Lines

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

  • nums1[i] == nums2[j], and
  • the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

int maxUncrossedLines(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int[][] f = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
            if (nums1[i - 1] == nums2[j - 1]) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    return f[m][n];
}

1312. Minimum Insertion Steps to Make a String Palindrome

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

public int minInsertions(String s) {
    int n = s.length();
    String sReverse = new StringBuilder(s).reverse().toString();

    return n - lcs(s, sReverse);
}

private int lcs(String s1, String s2) {
    int n = s.length();
    int[][] dp = new int[n + 1][n + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][n];
}

97. Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

给定三个字符串A, B, X

判断X是否是由A, B交错在一起形成

即A是X的子序列，去掉A后，剩下的字符组成B

状态：f[i][j]表示为X的前i+j个字符是否由A前i个字符和B前j个字符交错形成

转移：f[i][j]=(f[i-1][j]&&x[i+j-1]==A[i-1])||(f[i][j-1]&&x[i+j-1]==B[j-1])

边界：f[0][0]=true

优化：可以滚动数组优化到On

boolean isInterleave(String s1, String s2, String s3) {
    int n = s1.length(), m = s2.length();
    if (n + m != s3.length()) {
        return false;
    }
    boolean[][] f = new boolean[n + 1][m + 1];

    f[0][0] = true;
    for (int j = 1; j <= m; j++)  {
        f[0][j] = f[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
    }
    for (int i = 1; i <= n; i++) {
        f[i][0] = f[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        for (int j = 1; j <= m; j++) {
            int p = i + j;
            f[i][j] = f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p - 1) || 
                      f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p - 1);
        }
    }
    return f[n][m];
}

72. Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

状态：f[i][j]表示A前i个字符A[0,i-1]和B前j个字符[0,j-1]的Edit Distance

转移：f[i][j]=min{f[i-1][j]+1, f[i][j-1]+1, f[i-1][j-1]+1, f[i-1][j-1]|A[i-1]==B[j-1]}

边界：f[0][j]=0, f[i][0]=0

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] f = new int[m + 1][n + 1];
    for (int j = 0; j <= n; j++) {
        f[0][j] = j;
    }
    for (int i = 1; i <= m; i++) {
        f[i][0] = i;
        for (int j = 1; j <= n; j++) {
            f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
            }
        }
    }
    return f[m][n];
}

Distinct Subsequences 不同子序列

状态：f[i][j]表示A前i个字符A[0,i-1]含有B前j个字符[0,j-1]的不同子序列

转移：f[i][j]=f[i-1][j]+f[i-1][j-1]|a[i-1]==b[j-1]

边界：f[i][0]=1

答案：f[0][j]=0, f[i][0]=1

Regular Expression Matching 正则表达式匹配

状态：f[i][j]表示A前i个字符A[0..i-1]和B前j个字符B[0..j-1]能否匹配

转移：f[i][j]=f[i-1][j-1]&&match(a[i-1],b[j-1]), f[i][j-2]||f[i-1][j]&&match(a[i-1],b[j-2])

Wildcard Matching 通配符匹配

状态：f[i][j]表示A前i个字符A[0..i-1]和B前j个字符B[0..j-1]能否匹配

转移：f[i][j]=f[i-1][j-1]&&match(a[i-1],b[j-1]), f[i][j-2]||f[i-1][j]&&match(a[i-1],b[j-2])

最小的窗口子序列(字节)

给定字符串S和T，在字符串S中找到最短子串W，使得T是W的子序列。如果 S 没有包含 T 中的某个字符，则返回空字符串。如果有多个这样的最小长度子串，则 返回一个起点编号最小的。

状态：f[i][j]表示匹配 T串的前j个字符到S中前i个字符的子序列时的匹配起点

转移：f[i][j]=f[i-1][j-1]|s[i]==t[j],f[i-1][j]|s[i]!=t[j]

边界：f[i][1]=i|s[i]==t[1],f[i][0]=-1

答案：min_i{i-dp[i][m]+1|dp[i][m]!=-1]}

窗口长度为i-f[i][m]+1

dp结束后遍历 dp[][T.length()]，若 dp[i][T.length()] != 0， 则此处存在窗口起点 dp[i][T.length()]，窗口长度为 i – dp[i][T.length()] + 1 此时维护最小窗口长度 len 和窗口起点 start ， 答案为:S.substring(start, start + len)

David's Blog
Copyright © 2026 David Liu