动态规划

概念

将原问题分解为更小的子问题，(并且这些子问题包含公共的子子问题)并存储子问题的最优解，从而避免重复计算子问题

注意在算法中，子串和子序列的区别
子串要求连续，而子序列不要求连续

案例1. 最长回文子串
思路分析
定义一个二维数组dp[n][n]，dp[i][j]表示索引i到j的子串是否满足回文
dp[i][j]的取值分为下面三种情况
当i==j时，dp[i][j]=true
当j-i==1时，dp[i][j]=(src[i]==src[j])
当j-i>1时，dp[i][j]=(src[i]==src[j] && dp[i+1][j-1])

代码实现

public int getLongestPalindrome(String A, int n) {
    boolean[][] dp = new boolean[n][n];
    char[] c = A.toCharArray();
    int start = 0;// 保存最长回文子串的起点
    int max_length = 1; // 保存最长回文子串的长度
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            if (j - i < 2) {
                dp[i][j] = (c[i] == c[j]);
            } else {
                dp[i][j] = (c[i] == c[j] && dp[i + 1][j - 1]);
            }

            if (dp[i][j] && max_length < j - i + 1) {
                start = i;
                max_length = j - i + 1;
            }
        }
    }
    System.out.println(A.substring(start,max_length+start));
    return max_length;
}

案例1. 最长公共子串
思路分析
定义一个二维数组dp[n+1][m+1]，dp[i][j]表示当遍历到s1第i个数，同时遍历到字符串s2的第j个数时，最长公共子串的长度，则
当a[i-1]==b[j-1]时,dp[i][j]=dp[i-1][j-1]+1

代码实现

public int findLongest(String A, int n, String B, int m) {
    char[] a = A.toCharArray();
    char[] b = B.toCharArray();

    int[][] dp = new int[n + 1][m + 1];

    int max_length = 0;
    int end = 0; // 公共子串末尾
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (max_length < dp[i][j]) {
                    max_length = dp[i][j];
                    end = i;
                }
            }
        }
    }

    if (end - max_length >= 0)
        System.out.println(A.substring(end - max_length, end));

    return max_length;
}