    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int max = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(max, dp[i]);
        }

        return max;

    }

二.最长递增子序列

1.题目描述

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

力扣:力扣

2.问题分析

这里明确说了是连续的子序列,所以序列值应该是连在一起的,如:index=1,2,3

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

1.确定dp数组（dp table）以及下标的含义

dp[i]数组的含义是:以nums[i]为结尾的连续递增子序列的最大值

2.确定递推公式

这一题和上一题明显的不同就是连续与否,上一题如何nums[i]<nums[i-1],那么它的递增还有可能和i-1之前的数据构成递增序列,这一题,因为存在一个连续,所以如果nums[i]<nums[i-1],那么他肯定是不能构成连续递增序列了,因此这时dp[i]=1;如果nums[i]>nums[i-1],说明与前边的元素构成连续递增序列,因此dp[i]=dp[i-1]+1;

递推公式为:if (nums[i] > nums[i – 1]) dp[i] = dp[i – 1] + 1;

注意:这一题仍然需要dp数组中的最大值,原因和上一题一样

3.dp数组如何初始化

和上一题一样,所有的初始化为1

4.确定遍历顺序

和上一题一样,从左到右,但这一题只需要一层循环

5.举例推导dp数组

推导nums = [1,3,5,4,7]

i	0	1	2	3	4
dp[i]	1	2	3	1	2

最长连续递增序列为:{1,3,5}

3.代码实现

    public static int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        int max = 0;
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > nums[i - 1])
                dp[i] = dp[i - 1] + 1;
            max = Math.max(i, dp[i]);
        }
        return max;

    }

三.最长重复子数组

1.题目描述

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

力扣:力扣

2.问题分析

题目中说的就是子数组就是连续子序列

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

1.确定dp数组（dp table）以及下标的含义

因为这一题是两个数组,所以最好定义为二维数组

dp[i][j]的含义是:以nums1[i]结尾的A和以nums2[j]结尾的B,最长的公共子数组的长度是dp[i][j]

2.确定递推公式

子数组和连续子序列的含义是一样的,如果nums1[i]==nums2[j],此时只需要知道前边的最长的公共子数组的最大长度,就是dp[i-1][j-1](含义是以nums1[i-1]结尾的A和以nums2[j-1]结尾的B,最长的公共子数组的长度),此时+1便等于dp[i][j],如果不相等的话,这个时候公共子数组长度显然为0,不需要赋值

所以递推公式为:if (nums1[i] == nums2[j]) dp[i][j] = dp[i – 1][j – 1] + 1;

注意:这一题仍然需要dp数组中的最大值,原因和上一题一样

3.dp数组如何初始化

由递推公式可以知道由斜上方的元素推导出来的,所以至少要对第一行和第一列进行初始化赋值

具体的初始化代码如下:

        //对第一列进行初始化
        for (int i = 0; i < nums1.length; i++) {
            if (nums1[i] == nums2[0])
                dp[i][0] = 1;
            result = Math.max(result, dp[i][0]);
        }
        //对第一行进行初始化
        for (int j = 0; j < nums2.length; j++) {
            if (nums1[0] == nums2[j])
                dp[0][j] = 1;
            result = Math.max(result, dp[0][j]);
        }

4.确定遍历顺序

由递推公式可以看出,是由从上到下,从左到右进行遍历的

5.举例推导dp数组

对nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]进行推倒后的dp数组

[0, 0, 1, 0, 0]
[0, 1, 0, 0, 0]
[1, 0, 0, 0, 0]
[0, 2, 0, 0, 0]
[0, 0, 3, 0, 0]

3.代码实现

    public  int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        int result = 0;
        //对第一列进行初始化
        for (int i = 0; i < nums1.length; i++) {
            if (nums1[i] == nums2[0])
                dp[i][0] = 1;
            result = Math.max(result, dp[i][0]);
        }
        //对第一行进行初始化
        for (int j = 0; j < nums2.length; j++) {
            if (nums1[0] == nums2[j])
                dp[0][j] = 1;
            result = Math.max(result, dp[0][j]);
        }
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 1; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) { // 防止 i-1 出现负数
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                result = Math.max(result, dp[i][j]);
            }
        }

        return result;

    }

也可以进行这样设置 dp数组:以下标i – 1为结尾的A，和以下标j – 1为结尾的B，最长重复子数组长度为dp[i][j],这样的代码实现为 dp[i][0]和dp[0][j]没有意义,全部赋值为0 (推荐)

 public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int res = 0;
        for (int i = 1; i <= nums1.length; ++i) {
            for (int j = 1; j <= nums2.length; ++j) {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;


    }

4.代码的优化(滚动数组)

这样其实和01背包的二维数组优化成滚动数组一个思路,都是长度为nums2.length长的数组,然后第一个从左到右遍历,第二个从右到左遍历,为了不影响其他数据使用成为第二次推导出的数据

01背包指路:Java之动态规划的背包问题_允歆辰丶的博客-CSDN博客

第一个dp数组的含义:以nums2[j]为结尾的dp[j]:代码实现

  public int findLength4(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length];
        int result = 0;

        //对第一行进行初始化
        for (int j = 0; j < nums2.length; j++) {
            if (nums1[0] == nums2[j])
                dp[j] = 1;
            result = Math.max(result, dp[j]);
        }
        System.out.println(Arrays.toString(dp));
        for (int i = 1; i < nums1.length; i++) {
            for (int j = nums2.length - 1; j >= 0; --j) {
                if (nums1[i] == nums2[j]) { // 防止 i-1 出现负数
                    if (j == 0) {
                        dp[j] = 1;
                        continue;
                    }

                    dp[j] = dp[j - 1] + 1;
                    result = Math.max(result, dp[j]);
                } else {
                    dp[j] = 0;
                }
            }
            System.out.println(Arrays.toString(dp));
        }

        return result;


    }

第二种dp数组的含义:以nums2[j-1]为结尾的dp[j]:代码实现(推荐)

    public int findLength2(int[] nums1, int[] nums2) {
        int[] dp = new int[nums1.length + 1];
        int res = 0;
        for (int i = 1; i <= nums1.length; ++i) {
            for (int j = nums2.length; j >= 1; --j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else
                    dp[j] = 0;
                res = Math.max(dp[j], res);
            }
        }
        return res;


    }

四.最长公共子序列

1.题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

力扣:力扣

2.问题分析

子序列,显然是不连续的

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

1.确定dp数组（dp table）以及下标的含义

dp[i][j]的含义:长度为[0,i-1]的text1和长度为[0,j-1]的text2最最长公共子序列的长度为dp[i][j]

注意:这里不一定一定以text[i-1]结尾,只需要在[0,i-1]任意子字符串最长即可

2.确定递推公式

主要就是两种情况,一种就是text1.charAt(i-1)==text2.charAt(j-1);另一种是不相同

当相等的情况,很显然就是两个字符串长度各-1的最长公共子序列的长度+1,就是 dp[i][j]=dp[i-1][j-1]+1 例如(aab和bab,dp[2][2]=1,dp[3][3]=2)

当不相等的时候,就是text1[0,i-2]的text2和长度为[0,j-1]和text1[0,i-1]的text2和长度为[0,j-2]的最大值作为dp[i][j]的值

dp[i][j]=max(dp[i][j-1],dp[i-1][j])

                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }

3.dp数组如何初始化

因为dp[i][0]和dp[0][j]没有意义,所以初始化为0

,4.确定遍历顺序

由推导公式可以知道,遍历顺序是从左到右,从上到下的

5.举例推导dp数组

对于text1 = “abcde”, text2 = “ace” 进行推导

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]

最长公共子序列是 “ace” ，它的长度为 3 。

3.代码实现

    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        for (int i = 1; i <= text1.length(); ++i) {
            for (int j = 1; j <= text2.length(); ++j) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];

    }

4.代码优化(滚动数组)

    public int longestCommonSubsequence2(String text1, String text2) {
        int[] dp = new int[text2.length() + 1];

        for (int i = 1; i <= text1.length(); ++i) {
            int pre=dp[0];
            for (int j = 1; j <= text2.length(); ++j) {
                int cur = dp[j];
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[j] = pre + 1;
                else {
                    dp[j] = Math.max(cur, dp[j - 1]);
                }
                pre=cur;
            }
        }

        return dp[text2.length()];

    }

五.不相交的线

1.题目描述

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

nums1[i] == nums2[j]

且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

力扣:力扣

2.问题分析

这一题看样子题目意思改变了很多,其实和上一题字符串的意思是一样的,它规定是连线不可以相交的,其实意思就是i与j的相对位置是不可以改变的,比如nums1[i]==nums[j]了,那么这个时候你只能继续向后遍历,不可以反过来遍历,例如(nums1[i+1]==nums[j-1])这样是不行的,只能接着往后面相加,这样就和上一题的意思是一模一样的了

例如这一题:

5.举例推导dp数组

对于nums1 = [1,4,2], nums2 = [1,2,4]推导

[0, 1, 1, 1]
[0, 1, 1, 2]
[0, 1, 2, 2]

nums1[1]=4 到 nums2[2]=4,所以最多画两条线

3.代码实现

  public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; ++i) {
            for (int j = 1; j <= nums2.length; ++j) {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }

            }

        }
        return dp[nums1.length][nums2.length];


    }

4.代码优化(滚动数组)

    public static int maxUncrossedLines2(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length + 1];
        for (int i = 1; i <= nums1.length; ++i) {
            int pre = dp[0];
            for (int j = 1; j <= nums2.length; ++j) {
                int cur = dp[j];
                if (nums1[i - 1] == nums2[j - 1])
                    dp[j] = pre + 1;
                else {
                    dp[j] = Math.max(cur, dp[j - 1]);
                }
                pre = cur;

            }

        }

        return dp[nums2.length];
        
    }

六.最大子数组和

1.题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

力扣:力扣

2.问题分析

最大子数组说明是连续的

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

1.确定dp数组（dp table）以及下标的含义

dp[i]的含义是:以nums[i]结尾的子数组的最大和是dp[i]

2.确定递推公式

存在两种情况,一种就是i前边的最大子数组和加上nums[i],一种就是从只有nums[i],因为dp[i-1]可能存在已经是负值的情况,如果再加上nums[i],只会使值变小,这个时候从新从nums[i]开始更好,如果前边已经是正数了,加上nums[i](可能使dp[i-1]>dp[i],因为nums[i]可能为负数,因为dp数组定义的缘故,必须加入)

所以递推公式为:dp[i]=max(dp[i-1]+nums[i],nums[i]);

3.dp数组如何初始化

由递推公式可知,只需要初始化dp[0],因为子数组至少有一个值,所以dp[0]=nums[0];

4.确定遍历顺序

由递推公式可知,从左到右进行遍历

5.举例推导dp数组

对[-2,1,-3,4,-1,2,1,-5,4]进行推导

i	0	1	2	3	4	5	6	7	8
dp[i]	-2	1	-2	4	3	5	6	1	5

3.代码实现

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int res=nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res=Math.max(res,dp[i]);
        }
        return res;

    }

七.判断子序列

1.题目描述

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

力扣:力扣

2.问题分析

子序列:是不连续的问题,这一题其实和四.最长公共子序列差不多的问题,略有不同之后说明

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

1.确定dp数组（dp table）以及下标的含义

dp[i][j]的含义是:从[0,i-1]的子字符串s和从[0,j-1]的子字符串t,相同子序列的长度是dp[i][j]

注意:这里和第四题的dp数组还是有一点区别的

2.确定递推公式

主要也是分为两种情况,一种就是当s.charAt[i-1]==t.charAt[j-1],这个时候dp[i][j] = dp[i – 1][j – 1] + 1.这个时候相当于在i位置上的字符在t中找了第二种情况:s.charAt[i-1]!=t.charAt[j-1],这个时候就不能和第四题一样了,因为这一题是要找s是否为 t 的子序列,s数组如果你找到了几个字符在t中,你这个时候是不可以dp[i-1][j],这样就是s向前找,但是s还不可以删除的,例如s=”abc”c,t=”aacbc”,这个时候第一个a==a,然后b!=a,但这个时候你不可以使s字符串找到前边的a.

所以推导公式为:

if (s.charAt(i - 1) == t.charAt(j - 1))
    dp[i][j] = dp[i - 1][j - 1] + 1;
else {
    dp[i][j] = dp[i][j - 1];
}

3.dp数组如何初始化

由递推公式可知,dp[0][j]和dp[i][0]没有意义,初始化为0

4.确定遍历顺序

由递推公式可知,从前到后,从上到下

5.举例推导dp数组

对s = “abc”, t = “ahbgdc”进行推导

[0, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 2, 2, 2, 2]
[0, 0, 0, 0, 0, 0, 3]

3.代码实现

    public boolean isSubsequence(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 1; j <= t.length(); ++j) {
                if (s.charAt(i - 1) == t.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else {
                    dp[i][j] = dp[i][j - 1];
                }

            }
        }
      return dp[s.length()][t.length()]==s.length();
    }

4.双指针代码实现

当然,这一题也可以选择使用双指针来解决,代码实现

    public boolean isSubsequence2(String s, String t) {
        int j = 0;
        for (int i = 0; i < s.length(); ++i) {
            while (j < t.length() && s.charAt(i) != t.charAt(j)) {
                j++;
            }
            j++;
        }
        return j <= t.length();
    }

八.不同的子序列

1.题目描述

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

力扣:力扣

2.问题分析

这里和第七题有相似之处,但还是有一定的区别

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

1.确定dp数组（dp table）以及下标的含义

dp[i][j]的含义是:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]

2.确定递推公式

其实这一题和上一题一样,dp[i][j]还是分两种情况

一种:当s.charAt[i-1]==t.charAt[j-1],此时dp[i][j]由两部分组成

当t.charAt[j-1]来进行匹配出现次数的时候,这一部分为dp[i-1][j-1]

当t.charAt[j-1]不是匹配出现次数的时候,这一部分为dp[i-1][j]

另一种:当s.charAt[i-1]!=t.charAt[j-1],这个时候只有t.charAt[j-1]不是匹配出现次数的时候为dp[i-1][j]

                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }

3.dp数组如何初始化

首先我们需要先回顾一下dp数组的含义

dp[i][0]的含义是t数组为空的时候,以i-1结尾的s出现在t中的个数,因为t为空,这个时候赋值为1

dp[0][j]的含义是s数组为空,s出现在以j-1结尾的t中的个数,这个时候赋值为0

        for (int i = 0; i <= s.length(); ++i) {
            dp[i][0] = 1;
        }

4.确定遍历顺序

由递推公式可知,从前到后,从上到下

5.举例推导dp数组

对s = “rabbbit”, t = “rabbit”进行推导

[1, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0]
[1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 2, 1, 0, 0]
[1, 1, 1, 3, 3, 0, 0]
[1, 1, 1, 3, 3, 3, 0]
[1, 1, 1, 3, 3, 3, 3]

3.代码实现

    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i <= s.length(); ++i) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 1; j <= t.length(); ++j) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }

            }
        }
        return dp[s.length()][t.length()];

    }

九.两个字符串的删除操作

1.题目描述

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

力扣:力扣

2.问题分析

本题和上一题(八.不同的子序列)有相似之处,但又有不同之处,相同就是都有删除操作,上一题是只能删除s字符串,但是这一题两个字符串都可以进行删除操作

1.确定dp数组（dp table）以及下标的含义

dp[i][j]的含义是:以i-1为结尾的字符串word1子序列中出现以j-1为结尾的字符串word2,达到相同所需要删除的最小步数

2.确定递推公式

其实这一题和上一题一样,dp[i][j]还是分两种情况

当word1.charAt[i-1]==word2.charAt[j-1],这个时候就不需要进行删除操作,只需要前边的子字符串达到相同所需要的最小步数;即dp[i][j]=dp[i-1][j-1]

当word1.charAt[i-1]!=word2.charAt[j-1],这个时候可以进行三种操作使两个字符串达到相同

删除word1的第i-1个字符,使剩下的子字符串与word2[0-j-1]字符串达到相等的最小步数使相等,即dp[i][j]=dp[i-1][j]+1
删除word2的第j-1个字符,使剩下的子字符串与word1[0-i-1]字符串达到相等的最小步数使相等,即dp[i][j]=dp[i][j-1]+1
同时删除word1的第i-1个字符和word2的第j-1个字符,使两个字符串剩下的子字符串达到相等的最小步数使相等,即dp[i][j]=dp[i-1][j-1]+2

这个时候,其实可以进行简化操作,因为dp[i-1][j-1]+2=dp[i][j-1]+1(dp[i-1][j]+1),

因为删除两个字符的操作(dp[i-1][j-1]+1),可以从先删除一个字符的操作(dp[i][j-1]),然后手动删除一个字符(+1)的操作来完成

所以取两者最小值就是递推公式

                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }

3.dp数组如何初始化

由递推公式可以看出,至少要对dp[i][0]和dp[0][j]进行初始化操作

word1或者word2为空字符串,所以要全删除,代码如下

        for (int i = 1; i <= word1.length(); ++i) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= word2.length(); ++i) {
            dp[0][i] = i;
        }

4.确定遍历顺序

由递推公式可知,从前到后,从上到下

5.举例推导dp数组

对word1 = “sea”, word2 = “eat”进行推导

[1, 2, 3, 4]
[2, 1, 2, 3]
[3, 2, 1, 2]

3.代码实现

 public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word1.length(); ++i) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= word2.length(); ++i) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= word1.length(); ++i) {
            for (int j = 1; j <= word2.length(); ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }

            }
        }

        return dp[word1.length()][word2.length()];

    }

4.不同的dp定义实现

这一题其实可以根据四.最长公共子序列进行操作,因为所需要删除得到的最终就是两者的最长公共子序列,只需要两者长度相加减去最长公共子序列长度*2就是最终答案

    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word1.length(); ++i) {
            for (int j = 1; j <= word2.length(); ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }

            }
        }
        return word1.length()+word2.length() - dp[word1.length()][word2.length()]*2;
    }

十.编辑距离

1.题目描述

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

力扣:力扣

2.问题分析

1.确定dp数组（dp table）以及下标的含义

dp[i][j]的含义是:表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2,使其相同的最少操作数为dp[i][j]

2.确定递推公式

其实这一题和上一题一样,dp[i][j]还是分两种情况

当word1.charAt[i-1]==word2.charAt[j-1],这个时候不需要进行操作,只需要前边的子字符串达到相同的最小操作,即dp[i][j]=dp[i-1][j-1]

当word1.charAt[i-1]!=word2.charAt[j-1],这个时候就是用三种操作

删除操作1:word1删除一个字符,使其与word2相同,dp[i][j]=dp[i-1][j]+1
删除操作1:word2删除一个字符,使其与word1相同,dp[i][j]=dp[i][j-1]+1
添加操作:其实添加操作就是删除操作,可以想象,在word1添加一个字符,相当于word2删除一个字符,所以这时候不需要考虑
替换操作:将word1的i-1的字符替换为word2的j-1的字符,使其相同,dp[i][j]=dp[i-1][j-1]+1

取最小dp[i][j] = min(dp[i – 1][j], Math.min(dp[i][j – 1], dp[i – 1][j – 1])) + 1

       if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                 dp[i][j] = dp[i - 1][j - 1];
      } else {
           dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
           }

3.dp数组如何初始化

这题和上一题一样,都是初始化第一行第一列

        for (int i = 1; i <= word1.length(); ++i)
            dp[i][0] = i;
        for (int j = 1; j <= word2.length(); ++j)
            dp[0][j] = j;

4.确定遍历顺序

由递推公式可知,从前到后,从上到下

5.举例推导dp数组

对word1 = “horse”, word2 = “ros”进行推导

[0, 1, 2, 3]
[1, 1, 2, 3]
[2, 2, 1, 2]
[3, 2, 2, 2]
[4, 3, 3, 2]
[5, 4, 4, 3]

horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

3.代码实现

    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word1.length(); ++i)
            dp[i][0] = i;
        for (int j = 1; j <= word2.length(); ++j)
            dp[0][j] = j;
        for (int i = 1; i <= word1.length(); ++i) {
            for (int j = 1; j <= word2.length(); ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }

        }
        return dp[word1.length()][word2.length()];
    }

十一.回文子串

1.题目描述

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

力扣:力扣

2.问题分析

子字符串,首先明确是连续的子序列

1.确定dp数组（dp table）以及下标的含义

有关回文子串的递推公式和我们平时的认知有所区别,一般都是一维数组,但是这里要定义成二维的.

dp[i][j]的含义:字符串s从i到j的子字符串是否为回文子串,布尔类型的二维数组

2.确定递推公式

一共分为两种情况,一种s.charAt(i)==s.charAt(j),一种是不相等

不相等的情况很好判定,他直接就不是回文子串

如果相等的话,分为三种情况

i==j,这个时候一定是回文子串,例如子字符串”a”
i与j相差1的时候,这个时候也一定为回文子串,例如字符串”aa”
当i与j相差大于1的时候,这个时候就要判定dp[i+1][j-1]是否为回文子串,如果是true,则dp[i][j]=true,否认为false,例如字符串”abca”不是的,字符串”abba”是的

3.dp数组如何初始化

刚开始应该把所有的全部初始化为false

4.确定遍历顺序

由递推公式可知和上图可知,想要推导dp[i][j],需要先从上到下,然后内层循环从左到右,并且j需要大于等于i,这样才符合递推公式(i到j子字符串)

5.举例推导dp数组

对”abcaacde”进行推导

[true, false, false, false, false, false, false, false]
[false, true, false, false, false, false, false, false]
[false, false, true, false, false, true, false, false]
[false, false, false, true, true, false, false, false]
[false, false, false, false, true, false, false, false]
[false, false, false, false, false, true, false, false]
[false, false, false, false, false, false, true, false]
[false, false, false, false, false, false, false, true]

一共有10个回文子串

3.代码实现

    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int res = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            for (int j = i; j < s.length(); ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        res++;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        res++;
                    }
                }
            }
        }
        return res;

    }

4.中心扩展法代码实现

中心拓展法:每次选定一个中心,以他向外扩展,例如字符串”abbbabba”,选定中间的a为中心,向外拓展,第一次”bab”…..

但是这样有个问题,就是拓展出来的字符串的长度是奇数大小的,偶数长度的字符串无法加入到子字符串中,所以要考虑.那么我们考虑到单双中心点之后,我们要循环多次呢,首先单中心点事s.length()次,双中心点有s.length()-1次,所以一共有s.length()*2-1次,他每次的i可以center除以2来进行选定中心点,然后center为奇数时候为单中心点,为偶数时候为双中心点

具体代码如下:

    public int countSubstrings2(String s) {
        int res = 0;
        for(int center=0;center<s.length()*2-1;++center){
            int i=center/2;
            int j=i+center%2;
            while (i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j)){
                res++;
                i--;
                j++;
            }
        }

        return res;

    }

十二.最长回文子串

1.题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

力扣:力扣

2.问题分析

这一题和上一题的递推公式一样,只需要加一个判断,j-i大于target.length(),实时更新target的最长子字符串

3.代码实现

    public String longestPalindrome(String s) {
        String target = "";
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = s.length() - 1; i >= 0; --i) {
            for (int j = i; j < s.length(); ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        if (j - i >= target.length())
                            target = s.substring(i, j + 1);
                        dp[i][j]=true;
                    } else if (dp[i + 1][j - 1]) {
                        if (j - i >= target.length())
                            target = s.substring(i, j + 1);
                        dp[i][j]=true;
                    }
                }
            }
        }
        return target;

    }

4.中心扩展法代码实现

    public String longestPalindrome(String s) {
        String target = "";
        for (int center = 0; center < s.length() * 2 - 1; ++center) {
            int i = center / 2;
            int j = i + center % 2;
            while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
                if (j - i >= target.length())
                    target = s.substring(i, j + 1);
                i--;
                j++;
            }
        }
        return target;

    }

十三.最长回文子序列

1.题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

力扣:力扣

2.问题分析

1.确定dp数组（dp table）以及下标的含义

dp[i][j]的含义是:字符串在s在[i,j]范围内的最长回文子序列的长度为dp[i][j]=

2.确定递推公式

还是分为两种情况,当s.charAt(i)==s.charAt(j),这个时候dp[i][j]=dp[i+1][j-1]+2;

s.charAt(i)!=s.charAt(j),这个时候分为两种情况,一种是加入s.charAt(i)字符的情况: dp[i][j]=dp[i][j-1] 一种是就让s.charAt(j)字符的情况:dp[i][j]=dp[i+1][j]

                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }

3.dp数组如何初始化

需要初始化i与j相等的情况,由递推公式可以看出,递推公式是计算不到 i 和j相同时候的情况.

手动初始化为1,其他情况初始化为0即可

4.确定遍历顺序

由递推公式可知和上图可知,想要推导dp[i][j],需要先从上到下,然后内层循环从左到右,并且j需要大于等于i,这样才符合递推公式(i到j子字符串)

5.举例推导dp数组

对s=”bbbab“进行推导

[1, 2, 3, 3, 4]
[0, 1, 2, 2, 3]
[0, 0, 1, 1, 3]
[0, 0, 0, 1, 1]
[0, 0, 0, 0, 1]

一个可能的最长回文子序列为 “bbbb”

3.代码实现

    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];

        for (int i = s.length() - 1; i >= 0; --i) {
            dp[i][i] = 1; // 初始化
            for (int j = i + 1; j < s.length(); ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.length() - 1];
    }

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/101048.html