巩固一遍

适用原则 :

最优解
无后效性
子问题的重叠性

动态规划使用规则

确定状态
确定边值
确定状态转换方程

题目 :

求两个字符串最长公共连续子串长度
例如 : 字符串1 : "ABC" , 字符串2 : "A" , 公共子串 : "A", 长度1
例如 : 字符串1 : "ABC" , 字符串2 : "BCA" , 公共子串 : "BC", 长度2
例如 : 字符串1 : "ABCDEDCBA" , 字符串2 : "DED" , 公共子串 : "DED", 长度3

分析步骤

第一步 : 确定状态
第二步 : 确定边值
第三步 : 确定状态转移方程

第一步 : 确定状态

确定状态就要回归到动态规划的特性, 推导的特性, 从0到n.
因为这里是比较两个字符串, 所以需要用到两个数组, 关于最优解dp就是dp[i][j].

如果是比较一个数组里面的内容就是dp[i],
如果是比较三个数组里面的内容就是dp[i][j][k].
如果是比较N个数组里面的内容就是dp[i][j][k][..][..][..].....

从题意看, 我们需要从左往右遍历, 从上往下遍历两个字符串中的每一个字符.
因为这里将字符串拆分数组, 遍历的时候, 遍历条件也是一个一个的字符遍历,

这里遍历str1Arr和str2Arr , 从0到n推导 , dp[][] = new int[3][3]

比如 :

str1 = "ABC" ;
str2 = "BCA" ;   
char[] str1Arr = str1.toCharArray();
char[] str2Arr = str2.toCharArray();

这里n代表str1Arr中对应的坐标索引,
这里m代表str2Arr中对应的坐标索引,
分析dp[n][m].
(PS : n和m可以用i和j替换也可以, 一个意思)

n = 0, str2Arr[0] = "B"
dp[0][0] = 0 , dp[0][1] = 1, dp[0][2] = 0;

分析 : 因为"B"只有一个并且和str1中的第二个"B"相同, 所以dp[0][1] = 1.

n = 1, str2Arr[1] = "C"
dp[1][0] = 0 , dp[1][1] = 1, dp[1][2] = 2;

分析 :
因为"C"是第二个字符, 前面一个已经是"B", 如果前面的"B"已经有相等,并且紧接着后面的"C"也相等,也就是在上一个基础上加一, 这里的前一个的选择是对应的是"B","B"对应的是d[i-1][j-1], 所以dp[1][2] = dp[0][1] + 1 = 2;

如果能在上一个基础上加一, 也就是当前的字符跟上一个字符拼接得到的新字符串, 就是str1完整字符串的子串.肯定相等

简单粗暴分析 : 就是所以dp[i][j] = 最大值. 这个最大值就是当前最长的连续子串

n = 2, str2Arr[2] = "A"
dp[1][0] = 1 , dp[1][1] = 0, dp[1][2] = 0;

分析 : 同n=1

所以这里相等的话就在前一个基础上+1, 不相等就跳过.

PS : 这里主要是理解上一个基础上加一 , 这个上一个的选择.

也就是说 dp[i][j] 是 str1Arr 以[0 , i - 1]的范围内, str2Arr 以[0 , j - 1]的范围内的最优解

	Str1	A	B	C
Str2	-	-	-	-
B	-	0	1	0
C	-	0	0	2
A	-	1	0	0

第二步 : 确定边值

这里主要考虑第一个和最后一个的情况. 在代码中的判断注意下

第三步 : 确定状态转移方程

从第一步分析中.
因为"C"是第二个字符, 前面一个已经是"B", 如果前面的"B"已经有相等,并且紧接着后面的"C"也相等,也就是在上一个基础上加一, 这里的前一个的选择是对应的是"B","B"对应的是d[i-1][j-1], 所以dp[1][2] = dp[0][1] + 1 = 2;

也就是

if 判断当前字符相等 {
    dp[i][j] = dp[i-1][j-1] + 1;
} else {
    dp[i][j] = 0;// 默认初始化数组就是为0, 直接用continue代替
}

代码实现

  public static int LCSubSting(String str1, String str2) {
    char[] str1Arr = str1.toCharArray();
    char[] str2Arr = str2.toCharArray();

    int[][] dp = new int[str1Arr.length][str2Arr.length];
    int max = 0; // 记录最大值

    for (int i = 0; i < str1.length(); i++) {
      for (int j = 0; j < str2.length(); j++) {
        //比较规则
        if (str1Arr[i] == str2Arr[j]) {
          // 这里注意的是i=0,j=0的情况
          if (i == 0 || j == 0) {
            dp[i][j] = 1;
          } else {
            dp[i][j] = dp[i-1][j-1] +1;
          }
        } else {
          continue;
        }
        //最后比较最大的一个
        max = Math.max(max,dp[i][j]);
      }
    }
    return max;
  }

测试

例如 : 字符串1 : "ABC" , 字符串2 : "A" , 公共子串 : "A", 长度1

测试1

例如 : 字符串1 : "ABC" , 字符串2 : "BCA" , 公共子串 : "BC", 长度2

测试2

例如 : 字符串1 : "ABCDEDCBA" , 字符串2 : "DED" , 公共子串 : "DED", 长度3

测试3

如果两个长度特别长, 有需要打印其中最长的子串是什么. 稍微修改 :

public static String LCSubSting2(String str1, String str2) {
    char[] str1Arr = str1.toCharArray();
    char[] str2Arr = str2.toCharArray();

    int[][] dp = new int[str1Arr.length][str2Arr.length];
    int endIndex = 0 , max = 0;
    for (int i = 0; i < str1.length(); i++) {
      for (int j = 0; j < str2.length(); j++) {
        if (str1Arr[i] == str2Arr[j]) {
          if (i == 0 || j == 0) {
            dp[i][j] = 1;
          } else {
            dp[i][j] = dp[i-1][j-1] +1;
          }
        } else {
          continue;
        }

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

打印子串

复杂度分析

时间复杂度 , 两个for循环 , o(str1Arr.length * str2Arr.length)

总结 :

对于动态规划, 最主要的是dp, dp就是最优解, 对于dp怎么确定状态, 应该是比较抽象, 不太好理解. 那么就根据题意来从0推导.

自己总结 :

从0到n推导, 因为从0开始, 首先确定最基本的逻辑, 根据题意判断用多少个for循环.
不考虑中间值, 比如dp[i][j]代表什么意思, 如果是遍历一个数组, 那就dp是一维数组, 如果是遍历两个数组, 那dp就是二维数组. 以此类推.
从0到n推导后, 从中分析dp的状态转移方程.
确定判断条件.
写出对应的代码

算法-动态规划(2)最长公共子串