Double-Sequence DP Problem

Usually inputs are two strings or arrays

Subproblem can be represented as 2-dimentional arrays as f[i][j], usually representing the solutions to subproblem ending at position i of string A and position j of string B (第一个sequence的前i个元素配上第二个sequence的前j个元素)

Use 2-dimentional arrays f[n+1][m+1]

Need to initialize f[i][0] and f[0][j], and remember Java will automatically assign 0(for integers) or false(for boolean) for arrays

Longest Common Subsequence

We have a specific article for this topic, no more details here.

Edit Distance

Analysis:

Subproblem: f[i][j]: minimum steps needed to convert A(0,i-1) to B(0,j-1) (string A的前i个字符需要的多少次编辑转换为string B的前j个字符)
Initialize: f[i][0]=i, a string with length i needs to delete i times to become an empty string; f[0][j]=j, an empty string needs to insert j times to become a string with length j
Function: if A.charAt(i-1)==B.charAt(j-1), f[i][j]=f[i-1][j-2], no need to modification to last character; else, f[i][j]=MIN(f[i-1][j],f[i][j-1],f[i-1][j-1])+1, corresponding to deletion, insertion, replacement separately
Answer: f[A.length()][B.length()]

public int minDistance(String word1, String word2) {

        if (word1 == null)
            return word2.length();
        if (word2 == null)
            return word1.length();

        int M = word1.length();
        int N = word2.length();
        int[][] distance = new int[M+1][N+1];

        // Initialization
        distance[0][0] = 0;
        // Need to delete i characters to become an empty string
        for (int i=1; i<=M; i++) {
            distance[i][0] = i;
        }
        // Need to add j characters to become word2 from empty string
        for (int j=1; j<=N; j++) {
            distance[0][j] = j;
        }
        // Function
        for (int i=1; i<=M; i++) {
            for (int j=1; j<=N; j++) {
                distance[i][j] = Math.min(distance[i-1][j-1], 
                                    Math.min(distance[i-1][j], distance[i][j-1]))+1;
                if (word1.charAt(i-1) == word2.charAt(j-1))
                    distance[i][j] = distance[i-1][j-1];
            }
        }
        // Answer
        return distance[M][N];
    }

Distinct Subsequences

题目理解：计算S有多少个跟T相同的distinct subsequences

Analysis:

Subproblem: f[i][j]: S的前i个字符里选取T的前j个字符有多少方案
Initialize: f[i][0]=1, just one subsequence to match empty string; f[0][j]=0(j>0), empty string has no way offer a subsequence to match non-empty string
Function: if S.charAt(i-1)==T.charAt(j-1), f[i][j]=f[i-1][j-1]+f[i-1][j]; else, f[i][j]=f[i-1][j].

无论S[i-1]的字符与T[j-1]的字符是否相等，dp[i][j] >= dp[i-1][j].就是说，假设T已经匹配了i-1个字符，得到匹配个数为dp[i-1][j].现在无论S[i-1]是不是和T[j-1]匹配，匹配的个数至少是dp[i-1][j]。除此之外，当S[i-1]和T[j-1]相等时，还可以让S[i-1]和T[j-1]去匹配。
Answer: f[S.length()][T.length()]

public int numDistinct(String S, String T) {

        if (S == null || T == null)
            return 0;

        int M = S.length();
        int N = T.length();
        int[][] dp = new int[M+1][N+1];

        // Initialize
        // dp[0][0] = 1;
        for (int i=0; i<=M; i++) {
            dp[i][0] = 1;
        }
        for (int j=1; j<=N; j++) {
            dp[0][j] = 0;
        }
        // Function
        for (int i=1; i<=M; i++) {
            for (int j=1; j<=N; j++) {
                if (S.charAt(i-1) == T.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        // Answer
        return dp[M][N];
    }

Interleaving String

Analysis: The inputs are three strings but we don't need to build 3-dimentional arrays, cause i+j=position of the third string.

Subproblem: f[i][j]: if we can form string_3 ending at position i+j using first i chars of string_1 and j chars of string_2 (s1的前i个字符加上s2的前j个字符能否组成s3的前i+j个字符)
Initialize: f[0][0]=true; f[i][0]=(s1.charAt(i-1) == s3.charAt(i-1) && f[i-1][0] == true); f[0][j]=(s2.charAt(j-1) == s3.charAt(j-1) && dp[0][j-1] == true)

Function: **f[i][j]=(s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j])

          || (s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1])** (两个string中任意一个可以满足即可)

Answer: f[s1.length()][s2.length()]

public boolean isInterleave(String s1, String s2, String s3) {

        if (s1.length()+s2.length() != s3.length())
            return false;

        int M = s1.length();
        int N = s2.length();
        boolean[][] dp = new boolean[M+1][N+1];
        // Initialize
        // Other elements will be automatically assigned to false
        dp[0][0] = true;
        for (int i=1; i<=M; i++) {
            if (s1.charAt(i-1) == s3.charAt(i-1) && dp[i-1][0] == true)
                dp[i][0] = true;
        }
        for (int j=1; j<=N; j++) {
            if (s2.charAt(j-1) == s3.charAt(j-1) && dp[0][j-1] == true)
                dp[0][j] = true;
        }
        // Function
        for (int i=1; i<=M; i++) {
            for (int j=1; j<=N; j++) {
                if ((s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j])
                || (s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1]))
                    dp[i][j] = true;
            }
        }
        // Answer
        return dp[M][N];
    }

Double-Sequence DP Problem