LeetCode原题

• 算法
  • 1.动态规划：dp[i][j]表示str1[0,i-1]和str2[0,j-1]的最长公共子序列
  • 2.初始状态：dp[x][0] = 0, dp[0][x] = 0
  • 3.过渡公式：
    • 如果str1[i]==str2[j], dp[i][j] = dp[i-1][j-1] + 1;
    • 如果str1[i]!=str2[j], dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]);

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

• 算法
  • 1.空间优化
  • 2.考虑每轮外层循环更新dp数组需要那些值来使用辅助变量

public int longestCommonSubsequence(String text1, String text2) {
    int[] dp = new int[text2.length()+1];
    for (int i = 1; i <= text1.length(); i++) {
        int prev = dp[0], curr = dp[1];
        for (int j = 1; j <= text2.length(); j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) {
                dp[j] = prev + 1;
            } else {
                dp[j] = Math.max(curr, dp[j-1]);
            }
            if (j < text2.length()) {
                prev = curr;
                curr = dp[j+1];
            }
        }
    }
    return dp[text2.length()];
}

牛客本题

• 算法
  • 1.动态规划的过程中保存结果：伴随dp数组的StringDp数组跟随变化
  • 2.避免内存超限，这里使用优化后的空间复杂度来计算

public String LCS(String text1, String text2) {
    String[] stringDp = new String[text2.length()+1];
    for (int i = 0; i < stringDp.length; i++) {
        stringDp[i] = new String();
    }
    int[] dp = new int[text2.length()+1];
    for (int i = 1; i <= text1.length(); i++) {
        int prev = dp[0], curr = dp[1];
        String stringPrev = stringDp[0], stringCurr = stringDp[1];
        for (int j = 1; j <= text2.length(); j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) {
                dp[j] = prev + 1;
                stringDp[j] = stringPrev + text2.substring(j-1, j);
            } else {
                dp[j] = Math.max(curr, dp[j-1]);
                if (curr > dp[j-1]) {
                    dp[j] = curr;
                    stringDp[j] = stringCurr;
                } else {
                    dp[j] = dp[j-1];
                    stringDp[j] = stringDp[j-1];
                }
            }
            if (j < text2.length()) {
                prev = curr;
                curr = dp[j+1];
                stringPrev = stringCurr;
                stringCurr = stringDp[j+1];
            }
        }
    }
    return stringDp[text2.length()];
}

• 算法
  • 动态规划后根据dp数组回溯结果

public String LCS(String text1, String text2) {
    int length1 = text1.length(), length2 = text2.length();
    int[][] dp = new int[length1+1][length2+1];
    for (int i = 1; i <= text1.length(); i++) {
        for (int j = 1; j <= text2.length(); j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    StringBuilder result = new StringBuilder();
    int i = length1, j = length2;
    while (i > 0 && j > 0) {
        if (text1.charAt(i-1) == text2.charAt(j-1)) {
            result.append(text1.charAt(i-1));
            i--;
            j--;
        } else {
            if (dp[i][j-1] > dp[i-1][j]) {
                j--;
            } else {
                i--;
            }
        }
    }
    return result.reverse().toString();
}