Java之动态规划之子序列问题

布满荆棘的人生 2024-03-27 15:54 60阅读 0赞

**目录**

0.动态规划问题

一.最长递增子序列

1.题目描述

2.问题分析

3.代码实现

二.最长递增子序列

1.题目描述

2.问题分析

3.代码实现

三.本质上升子序列个数

1.题目描述

2.问题分析

3.代码实现

三.最长重复子数组

1.题目描述

2.问题分析

3.代码实现

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

四.最长公共子序列

1.题目描述

2.问题分析

3.代码实现

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

五.不相交的线

1.题目描述

2.问题分析

3.代码实现

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

六.最大子数组和

1.题目描述

2.问题分析

3.代码实现

六02.找到最大开销的子字符串

1.题目描述

2.问题分析

3.代码实现

六03.删除一次得到子数组最大和

1.题目描述

2.问题分析

3.代码实现

七.判断子序列

1.题目描述

2.问题分析

3.代码实现

4.双指针代码实现

八.不同的子序列

1.题目描述

2.问题分析

3.代码实现

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

1.题目描述

2.问题分析

3.代码实现

4.不同的dp定义实现

十.最优包含

1.题目描述

2.问题分析

3.代码实现

十一.编辑距离

1.题目描述

2.问题分析

3.代码实现

十二.回文子串

1.题目描述

2.问题分析

3.代码实现

4.中心扩展法代码实现

十三.最长回文子串

1.题目描述

2.问题分析

3.代码实现

4.中心扩展法代码实现

十四.最长回文子序列

1.题目描述

2.问题分析

3.代码实现

--------------------

## 0.动态规划问题 ##

**动态规划**(**D**ynamic **P**rogramming)算法的核心思想是:将大问题划分为小问题,进行解决，从而一步步获取最优解的处理算法

动态规划对于解决最优子结构啊和重叠子问题等问题时候,有着很好的应用

对于**动态规划问题**,大致可以分为以下几步:

1.  确定dp数组（dp table）以及下标的含义
2.  确定递推公式
3.  dp数组如何初始化
4.  确定遍历顺序
5.  举例推导dp数组

## 一.最长递增子序列 ##

### 1.题目描述 ###

> 给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。
> 
> **子序列** 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。

力扣:[力扣][Link 1]

### 2.问题分析 ###

这一题首先要理解子序列问题,子序列不一定是连续一段的数组(子数组),只需要它的序列是递增的即可(例如index=0,2,3)

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

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

**本题的dp数组定义不是根据题目直接来进行定义,需要根据题意进行变通定义**

**dp\[i\]数组的含义:以nums\[i\]为结尾的最长递增子序列长度为dp\[i\]**

**注意:这里一定要以nums\[i\]为结尾,不可去除这个元素**

**2.确定递推公式**

**位置i的元素最长的递增子序列等于位置从0到j-1位置上最长递增子序列+1的最大值**

**递推公式:if (nums\[i\] > nums\[j\]) dp\[i\] = max(dp\[i\], dp\[j\] + 1);**

**注意:这里dp\[i\] = max(dp\[i\], dp\[j\] + 1)是为了取dp\[i\]的最大值,并不是dp\[i\]和dp\[j\] + 1比较**

**注意:这里它的最大值并不一定出现在dp\[nums.length-1\]的位置,如何最后一个数字比前边的都小,而dp数组的定义必须以nums\[i\]为结尾,所有此时dp\[i\]的值可能为1,因为应该取dp数组元素的最大值**

**3.dp数组如何初始化**

**由题意可知,无论前边的nums\[j\]是否比nums\[i\]大,总有一个元素满足递增序列,就是它本身自己,所有每一个dp\[i\]都应该初始化为1**

**4.确定遍历顺序**

**因为最长递增子序列是从前到后递增,所以我们也应该从左到右进行遍历**

**5.举例推导dp数组**

**对**nums = \[10,9,2,5,3,7,101,18\]**进行推导**

它的最长的递增序列是\{2,3,7,101\}或者\{2,3,7,18\}

### **3.代码实现** ###

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]]` 就是连续递增子序列。

力扣:[力扣][Link 2]

### 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\]**

最长连续递增序列为:\{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.题目描述 ###

> 小 蓝 特别喜欢单调递增的事物。  
> 在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的， 则 成 为 这 个 字 符 串 中 的 一 个 单调递增子序列。  
> 例如， 在字符串lanqiao中,，如 果 取 出 字 符 n和 q，则 nq组 成 一 个 单调递增子序列。类似的单调递增子序列还有 lnq、i 、ano 等等。  
> 小蓝发现， 有 些 子 序列虽然位置不同， 但是字符序列是一样的， 例如取第二个字符和最后一个字符可以取到 a o, 取最后两个字符也可以取到 a o。小蓝认为他们并没有本质不同。  
> 对于一个字符串， 小蓝想知道， 本质不同的递增子序列有多少个？  
> 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 1、a、n、q、i 、o、ln、an、lq、aq、nq、ai 、lo、ao、no、io、lnq 、anq、lno、ano、aio。  
> 请问对于以下字符串的本质上升子序列的个数

### 2.问题分析 ###

待写

### 3.代码实现 ###

public long countIncreasing(String s) {
            //dp[i]的含义:以i为结尾的字符串的最长递增子序列的长度
            long[] dp = new long[s.length()];
            long sum = 0;
            Arrays.fill(dp, 1);
            for (int i = 1; i < dp.length; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (s.charAt(i) > s.charAt(j)) {
                        dp[i] += dp[j];
                    }
                    //去重操作
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i] = 0;
                    }
                }
                sum += dp[i];
    
            }
            return sum;
        }

## 三.最长重复子数组 ##

### 1.题目描述 ###

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

力扣:[力扣][Link 3]

### 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数组如何初始化**

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

![7d984004458646a99bdf5a2d828d890d.png][]

**具体的初始化代码如下:**

//对第一列进行初始化
            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长的数组,然后第一个从左到右遍历,第二个从右到左遍历,为了不影响其他数据使用成为第二次推导出的数据**

![49021bb472ce405abea2de8aa701d426.png][]

**01背包指路:**[Java之动态规划的背包问题\_允歆辰丶的博客-CSDN博客][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"` 的子序列。
> 
> 两个字符串的 **公共子序列** 是这两个字符串所共同拥有的子序列。

力扣:[力扣][Link 4]

### 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.确定遍历顺序**

![5fd7de6de9b3469b9f1a9059ac0728c7.png][]

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

**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]`
>  *  且绘制的直线不与任何其他连线（非水平线）相交。
> 
> 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
> 
> 以这种方法绘制线条，并返回可以绘制的最大连线数。

力扣:[力扣][Link 5]

### 2.问题分析 ###

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

**例如这一题**:

![561691b410974aecb384b4462a9ff888.png][]

**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` ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
> 
> **子数组** 是数组中的一个连续部分。

力扣:[力扣][Link 6]

### 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\]**进行推导**

### **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;
    
        }

## 六02.找到最大开销的子字符串 ##

### 1.题目描述 ###

> 给你一个字符串 `s` ，一个字符 **互不相同** 的字符串 `chars` 和一个长度与 `chars` 相同的整数数组 `vals` 。
> 
> **子字符串的开销** 是一个子字符串中所有字符对应价值之和。空字符串的开销是 `0` 。
> 
> **字符的价值** 定义如下：
> 
>  *  如果字符不在字符串 `chars` 中，那么它的价值是它在字母表中的位置（下标从 **1** 开始）。
>     
>      *  比方说，`'a'` 的价值为 `1` ，`'b'` 的价值为 `2` ，以此类推，`'z'` 的价值为 `26` 。
>  *  否则，如果这个字符在 `chars` 中的位置为 `i` ，那么它的价值就是 `vals[i]` 。
> 
> 请你返回字符串 `s` 的所有子字符串中的最大开销。

力扣:[力扣][Link 7]

### 2.问题分析 ###

这一题和上一题几乎一样,这一题只不过需要自己求出nums的值,当存在就是val中对应的值,不存在就是字母表中对应的索引,dp数组都一样

### 3.代码实现 ###

public int maximumCostSubstring(String s, String chars, int[] vals) {
            HashMap<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < vals.length; ++i) {
                map.put(chars.charAt(i), vals[i]);
            }
            //dp[i]的含义:以i结尾的最大子数组和
            int max = 0;
            int[] dp = new int[s.length() + 1];
            for (int i = 1; i <= s.length(); ++i) {
                int val = map.getOrDefault(s.charAt(i-1), s.charAt(i-1) - 'a' + 1);
                dp[i] = Math.max(val, dp[i - 1] + val);
                max = Math.max(dp[i], max);
    
            }
            return max;
    
        }

## 六03.删除一次得到子数组最大和 ##

### 1.题目描述 ###

> 给你一个整数数组，返回它的某个 **非空** 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
> 
> 注意，删除一个元素后，子数组 **不能为空**。

力扣:[力扣][Link 8]

### 2.问题分析 ###

这一题和上面的最大子数组和差不多,多了一个删除的操作,因为题目描述说我们可以进行依次可选的删除操作,所以分为两种情况

1.当我们不进行删除操作:

和最大子数组的题目一样,递推公式也是一样的

2.当我们进行一次删除操作:

两种情况,一次当我们删除的是当前的元素,一次是删除的是之前的元素

此时我们来考虑递推公式的设计,我们需要设计一个二维的数组,来标记是否删除一次了

dp\[i\]\[j\]:当以i结尾的arr\[i\](可被删除)进行删除j次最大子数组的和,j=0,1

### 3.代码实现 ###

class Solution {
        public int maximumSum(int[] arr) {
            if (arr.length == 1)
                return arr[0];
            int[][] dp = new int[arr.length][2];
            dp[0][0] = arr[0];
            dp[0][1] = arr[0] > 0 ? arr[0] : 0;
            int res = Integer.MIN_VALUE;
            for (int i = 1; i < arr.length; ++i) {
                dp[i][0] = Math.max(dp[i - 1][0] + arr[i], arr[i]);
                dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + arr[i]);
                res = Math.max(res, Math.max(dp[i][0], dp[i][1]));
            }
            return res;
        }
    }

dp\[i\]\[0\] = Math.max(dp\[i - 1\]\[0\] + arr\[i\], arr\[i\]);  
dp\[i\]\[1\] = Math.max(dp\[i - 1\]\[0\], dp\[i - 1\]\[1\] + arr\[i\]);

## 七.判断子序列 ##

### 1.题目描述 ###

> 给定字符串 **s** 和 **t** ，判断 **s** 是否为 **t** 的子序列。
> 
> 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，`"ace"`是`"abcde"`的一个子序列，而`"aec"`不是）。

力扣:[力扣][Link 9]

### 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 位带符号整数范围。

力扣:[力扣][Link 10]

### 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数组如何初始化**

![952c9dc383554529a5315e92e0c4d9dd.png][]

**首先我们需要先回顾一下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`**相同**所需的**最小步数**。
> 
> **每步** 可以删除任意一个字符串中的一个字符。

力扣:[力扣][Link 11]

### 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.题目描述 ###

> 我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。  
> 给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T？

**输入格式**  
输入两行，每行一个字符串。第一行的字符串为 S，第二行的字符串为 T。两个字符串均非空而且只包含大写英文字母。  
**输出格式**  
输出一个整数，表示答案。

### 2.问题分析 ###

根据题目的描述,可以明显的直到这是一道关于子序列的问题,还有关于字符串修改(区别于上一题的删除问题)的问题

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

**dp\[i\]\[j\]的含义是:以i-1为结尾的字符串S子序列中出现以j-1为结尾的字符串T,最少修改dp\[i\]\[j\]次使T串为S串的子序列串.**

**2.确定递推公式**

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

**当S.charAt\[i-1\]==T.charAt\[j-1\],这个时候就不需要进行修改操作,只需要前边的S的子字符串满足T子字符串的修改的最小步数即可;即dp\[i\]\[j\]=dp\[i-1\]\[j-1\]**

**当S.charAt\[i-1\]!=T.charAt\[j-1\],这个时候可以进行两种操作使两个字符串满足子序列的条件**

*  **修改S的第i-1个字符,使剩下的子字符串与T\[0-j-1\]字符串满足子字符串的最小步数,即dp\[i\]\[j\]=dp\[i-1\]\[**j-1**\]+1**
 *  **不使用S字符串的第i-1个字符,使剩下的子字符串与S\[0-i-1\]字符串满足子字符串条件即可,即dp\[i\]\[j\]=dp\[i-1\]\[**j**\]**

**这个时候,其实可以进行简化操作,因为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 (s.charAt(i - 1) != t.charAt(j - 1)) {//不相等的时候,修改第i个或者不选第i个
                 dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i - 1][j]);
              } else {//相等的时候
                  dp[i][j] = dp[i - 1][j - 1];
               }

**3.dp数组如何初始化**

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

**当T串为空串的时候,这个时候不需要修改S就可以使S串包含T串,dp\[i\]\[0\]=0**

**当S串为空串的时候,这个时候需要无论怎么修改S字符串都不能使T字符串为S字符串的子序列,因此我们只需要初始化一个达不到的值即可(考虑以下是否能初始化为**Integer.MAX\_VALUE**,这里不推荐,因为之后可能存在正溢出的情况).**

for (int i = 1; i <= n; ++i) {
                dp[0][i] = mm;
            }

**4.确定遍历顺序**

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

**5.举例推导dp数组**

**对**word1 = "ABCDEABCD", word2 = "XAABZ"**进行推导**

> \[0, 10, 10, 10, 10, 10\]  
> \[0, 1, 10, 10, 10, 10\]  
> \[0, 1, 2, 10, 10, 10\]  
> \[0, 1, 2, 3, 10, 10\]  
> \[0, 1, 2, 3, 4, 10\]  
> \[0, 1, 2, 3, 4, 5\]  
> \[0, 1, 1, 2, 4, 5\]  
> \[0, 1, 1, 2, 2, 5\]  
> \[0, 1, 1, 2, 2, 3\]  
> \[0, 1, 1, 2, 2, 3\]

### 3.代码实现 ###

public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String s = scanner.nextLine();
            int m = s.length();
            String t = scanner.nextLine();
            int n = t.length();
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= n; ++i) {
                dp[0][i] = m + 1;
            }
            for (int i = 1; i <= m; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (s.charAt(i - 1) != t.charAt(j - 1)) {//不相等的时候,修改第i个或者不选第i个
                        dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i - 1][j]);
                    } else {//相等的时候
                        dp[i][j] = dp[i - 1][j - 1];
                    }
    
                }
            }
    
            System.out.println(dp[m][n]);
    
        }

## 十一.编辑距离 ##

### 1.题目描述 ###

> 给你两个单词 `word1` 和 `word2`， *请返回将 `word1` 转换成 `word2` 所使用的最少操作数* 。
> 
> 你可以对一个单词进行如下三种操作：
> 
>  *  插入一个字符
>  *  删除一个字符
>  *  替换一个字符

力扣:[力扣][Link 12]

### 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` ，请你统计并返回这个字符串中 **回文子串** 的数目。
> 
> **回文字符串** 是正着读和倒过来读一样的字符串。
> 
> **子字符串** 是字符串中的由连续字符组成的一个序列。
> 
> 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

力扣:[力扣][Link 13]

### 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.确定遍历顺序**

![4d82c65b2d8a417baed4af320ee76927.png][]

**由递推公式可知和上图可知,想要推导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` 中最长的回文子串。
> 
> 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

力扣:[力扣][Link 14]

### 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` ，找出其中最长的回文子序列，并返回该序列的长度。
> 
> 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

力扣:[力扣][Link 15]

### 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.确定遍历顺序**

![2abc7d43fd9b4d4482beb8e7aade3298.png][]

**由递推公式可知和上图可知,想要推导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];
        }

[Link 1]: https://leetcode.cn/problems/longest-increasing-subsequence/
[Link 2]: https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
[Link 3]: https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
[7d984004458646a99bdf5a2d828d890d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c46ef16ae12b46c680141d603e00eb5c.png
[49021bb472ce405abea2de8aa701d426.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bfbfac5be3164e4d9e7ac00633b9c9cc.png
[Java_-CSDN]: https://blog.csdn.net/qq_64580912/article/details/128618341?spm=1001.2014.3001.5501
[Link 4]: https://leetcode.cn/problems/longest-common-subsequence/
[5fd7de6de9b3469b9f1a9059ac0728c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5d73949a7b1d4e1b958b9af16fb0ab72.png
[Link 5]: https://leetcode.cn/problems/uncrossed-lines/
[561691b410974aecb384b4462a9ff888.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/efdad11661ad4094b72227a422173a69.png
[Link 6]: https://leetcode.cn/problems/maximum-subarray/
[Link 7]: https://leetcode.cn/problems/find-the-substring-with-maximum-cost/description/
[Link 8]: https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/description/
[Link 9]: https://leetcode.cn/problems/is-subsequence/
[Link 10]: https://leetcode.cn/problems/distinct-subsequences/
[952c9dc383554529a5315e92e0c4d9dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/81eb98ae19e04b999a03dbc079ebea2d.png
[Link 11]: https://leetcode.cn/problems/delete-operation-for-two-strings/
[Link 12]: https://leetcode.cn/problems/edit-distance/
[Link 13]: https://leetcode.cn/problems/palindromic-substrings/
[4d82c65b2d8a417baed4af320ee76927.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/edcd70247c4e4731adf2db3d60f76cc8.png
[Link 14]: https://leetcode.cn/problems/longest-palindromic-substring/description/
[Link 15]: https://leetcode.cn/problems/longest-palindromic-subsequence/
[2abc7d43fd9b4d4482beb8e7aade3298.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/826196c2522041d38fedae67bec33b04.png