动态规划

最长公共子串

这是一个典型的动态规划问题。

• 最优子结构

  在自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖于它们解的原问题自然也是全局最优解。

• 重复子问题

  递归地寻找子问题的最优解时，子问题会重叠地出现在子问题里，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。

动态规划解题步骤：

1. 定义子问题
2. 写出子问题的递推关系
3. 确定DP数组的计算顺序

本题中的具体表现为：

dp[i][j] 表示以str1以i结尾， str2以[j]结尾的子串的公共尾巴。
dp[i][j] = dp[i - 1][j - 1] + 1 或者0;

if(str1.charAt(0) == str1.charAt(0)) dp[0][0] = 1;
else dp[0][0] = 0;
if(str1.charAt(0) == str1.charAt(1)) dp[0][1] = 1;
else dp[0][1] = 0;
if(str1.charAt(1) == str1.charAt(0)) dp[1][0] = 1;
else dp[1][0] = 0;

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int tail = 0;
        int[][] dp = new int[str1.length()][str2.length()];
        if(str1.charAt(0) == str1.charAt(0)) dp[0][0] = 1;
        else dp[0][0] = 0;
        if(str1.charAt(0) == str1.charAt(1)) dp[0][1] = 1;
        else dp[0][1] = 0;
        if(str1.charAt(1) == str1.charAt(0)) dp[1][0] = 1;
        else dp[1][0] = 0;
        int max = 1;
        for(int i = 1; i < str1.length(); i++){
            for(int j = 1; j < str2.length(); j++){
                if(str1.charAt(i) == str2.charAt(j)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                    if(dp[i][j] > max){
                        tail = j;
                        max = dp[i][j];
                    }
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        return str2.substring(tail - max + 1, tail + 1);
    }
}