动态规划

1. 确定边界条件 str1[i] = str2[0] 得到 dp[i][0] = 1 str1[0] == str2[j] dp[0][j] = 1

2. i j 代表以i j 结尾的公共字符串 必须包含 i j

3. 所以 str[i] 不等于 str2[j] 时 dp[i][j] = 0

str[i] 等于str[j]      str[i][j] = str[i-1][j-1]+1 

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) {
        if(str1==null||str2==null||str1.equals("")||str2.equals("")){
            return "";
        }
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        int[][] dp = getdp(arr1,arr2);
        int max = 0;
        int end = 0;
        int m = arr1.length;
        int n = arr2.length;
        for(int i = 0;i<m;i++){
            for(int j=0;j<n;j++){
//                 找到最大值  更新 max end 
                if(dp[i][j]>max){
                    end = i;
                    max = dp[i][j];
                }
            }
        }
        
        return str1.substring(end-max+1,end+1);
        // write code here
    }
    
    public int[][] getdp(char[] arr1,char[] arr2){
        int m = arr1.length;
        int n = arr2.length;
        int[][] dp = new int[m][n];
        for(int i = 0;i<m;i++){
            if(arr1[i] == arr2[0]){
                dp[i][0] = 1;
            }
        }
        for(int j = 0;j<n;j++){
            if(arr1[0] == arr2[j]){
                dp[0][j] = 1;
            }
        }
        for(int i = 1;i<m;i++){
            for(int j = 1;j<n;j++){
                if(arr1[i] == arr2[j]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
            }
        }
        return dp;
    }
}