动态规划解决

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤，
动态规划三部曲
  • 定义数组元素的含义
我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
  • 找出数组元素之间的关系式
动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。
  • 找出初始值
学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。
————————————————————————————————————————————————
对应于本题，如果本题是求最长公共子串的长度，会更简单一些。因为不需要记录最长公共子串最后一个元素在字符串最后一个元素在字符串str1中的位置。如果要返回公共子串的内容，只需要记录最长公共子串最后一个元素在字符串最后一个元素在字符串str1中的位置就好了。这个如何实现呢？就是在递归的过程中比较当前dp[i][j]和记录的最长公共子串的长度大小，dp[i][j]大，说明记录的最长公共子串的长度需要更新了。
  • 定义数组元素的含义
         int[][] dp = new int[str1.length() + 1][str2.length() + 1];dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。
  • 找出数组元素之间的关系式

        要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元素所构成的最长公共子串，我们首先需要判断这两个字符是否相等。如果不相等，那么他们就不能构成公共子串，也就是dp[i][j]=0;如果相等，我们还需要计算前面相等字符的个数，其实就是dp[i-1][j-1]，所以dp[i][j]=dp[i-1][j-1]+1。

  • 找出初始值
    dp[0][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) {
    int maxLenth = 0;//记录最长公共子串的长度（维护一个最大值）
    int maxLastIndex = 0;//记录最长公共子串最后一个元素在字符串str1中的位置
    int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    for (int i = 0; i < str1.length(); i++) {
        for (int j = 0; j < str2.length(); j++) {
            if (str1.charAt(i) == str2.charAt(j)) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                //如果遇到了更长的子串，要更新，记录最长子串的长度，以及最长子串最后一个元素的位置
                if (dp[i + 1][j + 1] > maxLenth) {
                    maxLenth = dp[i + 1][j+1];
                    maxLastIndex = i;//这里是i而不是i+1
                }
            } else {
                dp[i + 1][j+1] = 0;
            }
        }
    }
    return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
}
}