【力扣刷题】Day31——DP专题

---

上一篇文章：【力扣刷题】Day30——DP专题_塔塔开!!!的博客-CSDN博客

• 动态规划章节到此就算完结啦，出了代码随想录路线的题外，自己还多找了一些类似的题目，好多题的状态转移真的很难想到，不看题解不看视频，一时半会还真的难理解。
• 有些题除了DP能解之外自己还扩展了一些其他解法，如传统的暴力枚举，双指针等等
• 后续还要再多扩展刷题、回顾二刷三刷之类的！

七、子序列问题（线性DP and 区间DP）

1、子序列（不连续）

29.最长递增子序列（LIS）

题目链接：300. 最长递增子序列 - 力扣（LeetCode）

状态表示：f[i]：包含i的前i之前的以nums[i]结尾的最长上升子序列长度

状态计算：由于是不连续的，我们考虑最后一个，要计算f[i]就要全部考虑nums[0 ~ i-1]即 j来枚举nums[0~i-1]，

if(nums[i] > nums[j])

 	f[i] = max(f[i], f[j] + 1)
1
2
3

初始化：当只有一个数是最长上升子序列的长度为1

for(int i = 0; i < n; i ++) f[i] = 1;
1

最后的答案：最长的递增子序列长度要从0~n-1的f[i]中取最大的

Code

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 10];

        for(int i = 0; i < n; i ++) f[i] = 1;
        
        int res = 0;
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < i; j ++){
                if(nums[i] > nums[j]){
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            res = Math.max(res, f[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

30. 最长公共子序列 （LCS）

题目链接：1143. 最长公共子序列 - 力扣（LeetCode）

思路：

注意：我们的下标是从1开始的！

考虑最后一个字符A[i]和B[j]

初始化：

A[0, i-1]和空串的最长公共子序列自然是0，所以f[i][0] = 0;

同理f[0][j]也是0。

Code

class Solution {
    public int longestCommonSubsequence(String A, String B) {
        int n = A.length();
        int m = B.length();
        A = " " + A;// 我们是下标从1开始
        B = " " + B;
        int[][] f = new int[n + 10][m + 10];
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                if(A.charAt(i) == B.charAt(j)){
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[n][m];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

31.不相交的线

题目链接：1035. 不相交的线 - 力扣（LeetCode）

要求相等且不相交且要最长的———— 其实就是最长公共子序列！

Code

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int[][] f = new int[n + 10][m + 10];
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                if(nums1[i - 1] == nums2[j - 1]){
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[n][m];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2、子序列（连续）

32. 最长连续递增序列

题目链接：674. 最长连续递增序列 - 力扣（LeetCode）

状态表示：f[i]：表示包含i的以nums[i]结尾的最长连续递增序列的长度为f[i]

由于是连续的我们就只要比较相邻前后两个元素即可，不用像不连续的最长递增子序列那样与j : 0~i-1上的数进行比较

状态计算：

if(nums[i] > nums[i - 1]) f[i] = f[i - 1] + 1;

初始化：

当只有一个数时最长连续递增序列长度即为1

for(int i = 0; i < n; i ++) f[i] = 1;
1

最后的结果：所有f[i]中的最大者

Code

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 10];
        for(int i = 0; i < n; i ++) f[i] = 1;

        int res = f[0];
        for(int i = 1; i < n; i ++){
            if(nums[i] > nums[i - 1]){
                f[i] = f[i - 1] + 1;
            }
            res = Math.max(res, f[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

33.最长重复子数组(TODO)

题目链接：718. 最长重复子数组 - 力扣（LeetCode）

这题不能误以为是求的最长公共子序列！子数组的意思就是连续的，而子序列不一定要连续！！

状态表示：f[i][j]：nums1[0~i-1]以nums1[i - 1]结尾的和nums2[0~j-1]以nums2[j - 1]结尾的最长重复子数组长度为f[i][j]

属性：Max_count

初始化：

根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！（-1怎么结尾呢是吧）

但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;

所以dp[i][0] 和dp[0][j]初始化为0。

为啥是以nums[i - 1/ j - 1]为结尾最为判断的依据呢？ 状态转移比较方便

Code

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] f = new int[n + 10][m + 10];
        for(int i = 0; i < n; i ++)  Arrays.fill(f[i], 0);

        int res = 0;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                if(nums1[i - 1] == nums2[j - 1]){
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }
                res = Math.max(res, f[i][j]);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

另一种状态表示的写法：

f[i][j]：表示nums1[0~i]，nums2[0~j]分别以nums1[i]和nums2[j]结尾的最长重复子数组长度为f[i][j]

初始化：就需要特殊处理了（存在只有单个连续的一个数相同情况），相比于上一张状态表示，下面这种初始化就需要考虑好了，具体看下面代码：

Code

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] f = new int[n + 10][m + 10];
        for(int i = 0; i < n; i ++) Arrays.fill(f[i], 0);
        int res = 0;
        // 初始化
        for(int i = 0; i < n; i ++){
            if(nums1[i] == nums2[0]){
                f[i][0] = 1;
                res = Math.max(f[i][0], res);    
            }
                
        }
        for(int i = 0; i < m; i ++){
            if(nums1[0] == nums2[i]){
                f[0][i] = 1;
                res = Math.max(f[0][i], res);
            }
        }

        for(int i = 1; i < n; i ++){
            for(int j = 1; j < m; j ++){
                if(nums1[i] == nums2[j]){
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }
                res = Math.max(res, f[i][j]);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

34. 最大子序和

题目链接：53. 最大子数组和 - 力扣（LeetCode）

思路一：两重枚举——超时

• 时间复杂度：O(n * n)

Code

class Solution {
    public int maxSubArray(int[] nums) {
        int res = -0x3f3f3f3f;
        for(int i = 0; i < nums.length; i ++){
            int sum = 0;
            for(int j = i; j < nums.length; j ++){
                sum += nums[j];
                res = Math.max(res, sum);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

思路二：动态规划——最大连续子段和

状态表示f[i]：表示以nums[i]结尾的最大连续子段和，f[i]只与f[i - 1]有关

属性：Max

假设数组 nums 的值全都严格大于 0，那么一定有 f[i] = f[i - 1] + nums[i]。

状态转移：但由于存在负数的情况，因此要分类讨论：

• f[i - 1] <= 0，那么f[i]要是加上它反而变小了，为此f[i] = nums[i]
• f[i - 1] > 0，那么 f[i] = f[i - 1] + nums[i]

初始化：f[0] = nums[0]，以nums[0]结尾的和即为它本身。

时间复杂度：O(n)

Code

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 10];
        f[0] = nums[0];
        for(int i = 1; i < n; i ++){
            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
        }
        int res = -0x3f3f3f3f;
        for(int i = 0; i < n; i ++) res = Math.max(res, f[i]);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

思路三：分治法求最大子段和

在区间[l, mid, r]中最大字段和可以分为三部分：

• 最大子段和在左边
• 最大子段和在右边边
• 最大子段和在中间

最终的答案：res = max(leftSum, rightSum, midSum)

Code

class Solution {
    static int res = -0x3f3f3f3f;
    static int MIN_VALUE = -0x3f3f3f3f;

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int result = findMaxSum(nums, 0, n - 1);
        return result;
    }
    /**
        返回最大子段和
     */
    public static int findMaxSum(int[] nums, int l, int r){
        if(l == r) return nums[l];

        int mid = (l + r) / 2;
        int leftSum = findMaxSum(nums, l, mid);
        int rightSum = findMaxSum(nums, mid + 1, r);
        res = Math.max(leftSum, rightSum);
        int midSum = findMidSum(nums, l, mid, r);
        res = Math.max(res, midSum);
        return res;
    }
    /**
        获取在中间部分的最大值
     */
     public static int findMidSum(int[] nums, int l, int mid, int r){
         // 左
         int left_max = MIN_VALUE;
         int l_sum = 0;
         for(int i = mid; i >= l; i --){
             l_sum += nums[i];
             left_max = Math.max(l_sum, left_max);
         }

        // 右
         int right_max = MIN_VALUE;
         int r_sum = 0;
         for(int i = mid + 1; i <= r; i ++){// 右边从mid + 1开始
             r_sum += nums[i];
             right_max = Math.max(r_sum, right_max);
         }

         return left_max + right_max;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

3、编辑距离

最短编辑距离

题目链接：902. 最短编辑距离 - AcWing题库

思路：和LCS很相像，我们依据从最后一步进行考虑

有三个操作，因此有三个子集！

状态表示 dp[i][j]

• 集合 ： 所有吧a中的前i个字母 变成 b中前j个字母的集合的操作集合
• 属性 ： 所有操作中操作次数最少的方案的操作数

状态计算
状态划分 以对a中的第i个字母操作不同划分

• 在该字母之后添加

  • 添加一个字母之后变得相同，说明没有添加前a的前i个已经和b的前j-1个已经相同
  • 即 ： dp[i][j] = dp[i][j-1] + 1

• 删除该字母

  • 删除该字母之后变得相同，说明没有删除前a中前i-1已经和b的前j个已经相同
  • 即 ： dp[i][j] = dp[i-1][j] + 1

• 替换该字母

  • 替换存在两种情况：结尾字母不同；结尾字母相同；
    • 若a[i] == b[j]，啥也不做，即： dp[i][j] = dp[i-1][j-1]
    • 若应结尾字母不相同，直接替换即可
      即：dp[i][j] = dp[i-1][j-1] + 1

时间复杂度：O(n * n)

Code

import java.io.IOException;
import java.util.*;

public class Main {
    static int N = 1010;
    static int[][] f = new int[N][N];

    public static void main(String[] args) throws IOException {
        //BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String a = scan.next();
        int m = scan.nextInt();
        String b = scan.next();
        
        a = " " + a;// 下标从1开始
        b = " " + b;

        // 初始化
        for(int i = 0; i <= n; i ++) f[i][0] = i;// 当b为空时 a只能进行删除操作
        for(int i = 0; i <= m; i ++) f[0][i] = i;// 当a为空时 a只能进行添加操作

        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + (a.charAt(i) == b.charAt(j) ? 0 : 1));
            }
        }
        System.out.println(f[n][m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

编辑距离

题目链接：899. 编辑距离 - AcWing题库

上一题的应用，让你求s串在限制操作次数limit下能变化为strings[]中的哪些串，统计这些串的个数。

我们肯定是想要在最少操作次数的情况下，与strings[]中的串进行匹配，操作仍然是增加、删除、替换。

Code

import java.io.IOException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        //BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int m = scan.nextInt();
        String[] s = new String[n + 10];
        for(int i = 0; i < n; i ++){
            s[i] = scan.next();
        }
        while(m -- > 0){
           String str = scan.next();
           int limit = scan.nextInt();

           // 遍历字符串数组，寻找能够匹配的串
            int res = 0;
            for(int i = 0; i < n; i ++){
                if(min_edit(str, s[i]) <= limit){
                    res ++;
                }
            }
            System.out.println(res);
        }
    }

    private static int min_edit(String a, String b) {
        int la = a.length();
        int lb = b.length();
        a = " " + a;
        b = " " + b;

        // 初始化
        int[][] f = new int[la + 10][lb + 10];
        for(int i = 0; i <= la; i ++) f[i][0] = i;
        for(int i = 0; i <= lb; i ++) f[0][i] = i;

        for(int i = 1; i <= la; i ++){
            for(int j = 1; j <= lb; j ++){
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + (a.charAt(i) == b.charAt(j) ? 0 : 1));
            }
        }
        return f[la][lb];
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

35.判断子序列

题目链接：392. 判断子序列 - 力扣（LeetCode）

Code

思路一：双指针

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        int n = s.length();
        int m = t.length();
        int len = 0;

        while(i < n && j < m){
            if(s.charAt(i) == t.charAt(j)){
                i ++;
                j ++;
                len ++;
            }else {
                j ++;
            }
        }
        return len == n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路二：子序列问题可以联想到动态规划

我们可以求两个串的最长公共子序列，然后判断最长公共子序列的长度是否等于s串的长度即可。

Code

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length();
        int m = t.length();
        s = " " + s;
        t = " " + t;
       
       int[][] f = new int[n + 10][m + 10];

       for(int i = 1; i <= n; i ++){
           for(int j = 1; j <= m; j ++){
               if(s.charAt(i) == t.charAt(j)){
                   f[i][j] = f[i - 1][j - 1] + 1;
               }else {
                   f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
               }
           }
       }
       return f[n][m] == n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

另一种思考方式：我们采用编辑距离的思考方式来实现（本身它的状态转移方程就跟LCS很相像），而这里我们统计的是相同子序列的长度，而不是操作的次数！

状态表示：

f[i][j] 表示以下标i为结尾的字符串s，和以下标j为结尾的字符串t，相同子序列的长度为f[i][j]

在确定递推公式的时候，首先要考虑如下两种操作（考虑最后一步），整理如下：

• if (s[i ] == t[j])
  • t中找到了一个字符在s中也出现了
• if (s[i] != t[j])
  • 相当于t要删除元素，继续匹配（为什么不能删除s[i]呢？ 因为我们要找的是t中有无完整的s，你删去了就不合理了）

状态计算：

• if (s[i] == t[j ])，那么f[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在f[i-1][j-1]的基础上加1

• if (s[i ] != t[j])，此时相当于t要删除元素，t如果把当前元素t[j ]删除，使得s[1~i]与t[1 ~ j-1]相匹配！即f[i][j] = dp[i][j - 1];

Code

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length();
        int m = t.length();
        s = " " + s;
        t = " " + t;
       
       int[][] f = new int[n + 10][m + 10];

       for(int i = 1; i <= n; i ++){
           for(int j = 1; j <= m; j ++){
               if(s.charAt(i) == t.charAt(j)){
                   f[i][j] = f[i - 1][j - 1] + 1;
               }else {
                   f[i][j] = f[i][j - 1];// 修改一下 也是可以通过的！
               }
           }
       }
       return f[n][m] == n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

36.不同的子序列（计数）

题目链接：115. 不同的子序列 - 力扣（LeetCode）

由于s串是模板串，我们应该是以他为基准！

Code

class Solution {
    public int numDistinct(String s, String t) {
        int n = s.length();
        int m = t.length();
        s = " " + s;
        t = " " + t;

        int[][] f = new int[n + 10][m + 10];
        for(int i = 0; i <= n; i ++){
            f[i][0] = 1;
        }
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                f[i][j] = f[i - 1][j];// 不选s[i]
                if(s.charAt(i) == t.charAt(j)){// 选s[i]
                    f[i][j] += f[i - 1][j - 1];
                }
            }
        }
        return f[n][m];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

37. 不同的子序列II（计数）

题目链接：940. 不同的子序列 II - 力扣（LeetCode）

不同的子序列的这两道题是真的绕，一时半会理解不过来了，qwq…

状态表示：f[i][j]：s[1~i]的字符中，以j（a~z : 0~26）为结尾的字符串中 构成不同非空子序列的所有集合

属性：count

状态计数（考虑最后一个）：

• 当s[i] != j，f[i][j] = f[i - 1][j]

• 当s[i] == j时，f[i][j] = 所有(f[i - 1][k(s[i] - 'a')]) + 1。以j为结尾的这个j可能不止出现一次

  --------ai

  -----j----j

初始化：前0个字符26种字母结尾的子序列的个数，默认值为0;

最后总的方案数：res += (f[n][0~26])

Code

class Solution {
    public int distinctSubseqII(String s) {
        int mod = (int)1e9 + 7;
        int n = s.length();
        s = " " + s;

        int[][] f = new int[n + 10][26];
        for(int i = 1; i <= n; i ++){
            int c = s.charAt(i) - 'a';
            for(int j = 0; j < 26; j ++){
                if(j != c){
                    f[i][j] = f[i - 1][j];
                }else {
                    int cur = 1;
                    for(int k = 0; k < 26; k ++) cur = (cur + f[i - 1][k]) % mod;
                    f[i][j] = cur;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < 26; i ++) res = (res + f[n][i]) % mod;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

题目链接：583. 两个字符串的删除操作 - 力扣（LeetCode）

和不同的子序列I相比，本题是两个字符串都可以删除，还是和编辑距离一样的思考方式

初始化：

• 当字符串a为空时，只能对字符串b进行删除操作
• 当字符串b为空时，只能对字符串a进行删除操作

Code

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        word1 = " " + word1;
        word2 = " " + word2;

        int[][] f = new int[n + 10][m + 10];
        for(int i = 0; i <= n; i ++) f[i][0] = i;
        for(int i = 0; i <= m; i ++) f[0][i] = i;

        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                if(word1.charAt(i) == word2.charAt(j)){
                    f[i][j] = f[i - 1][j - 1];
                }else {
                    f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 2);
                }
            }
        }
        return f[n][m];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

39.编辑距离

题目链接：72. 编辑距离 - 力扣（LeetCode）

上述最短编辑距离原题。

Code

class Solution {
    public int minDistance(String a, String b) {
        int n = a.length();
        int m = b.length();
        a = " " + a;
        b = " " + b;
        int[][] f = new int[n + 10][m + 10];

        // 初始化
        for(int i = 0; i <= n; i ++) f[i][0] = i;
        for(int i = 0; i <= m; i ++) f[0][i] = i;

        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + (a.charAt(i) == b.charAt(j) ? 0 : 1));
            }
        }
        return f[n][m];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、回文（区间DP）

对于一个子序列而言，如果它是回文子序列，并且长度大于 2，那么将它首尾的两个字符去除之后，它仍然是个回文子序列。因此可以用动态规划的方法完成一些经典的回文串最优性问题

40.回文子串

题目链接：647. 回文子串 - 力扣（LeetCode）

Code

思路一：暴力枚举所有子串，然后统计回文字串的个数，居然没有超时

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int res = 0;
        for(int i = 0; i < n; i ++){
            for(int j = i; j < n; j ++){
                String tmp = s.substring(i, j + 1);
                if(is_huiwen(tmp)){
                    res ++;
                }
            }
        }
        return res;
    }
    
    public boolean is_huiwen(String s){
        int i = 0;
        int j = s.length() - 1;
        while(i < j){
            if(s.charAt(i) == s.charAt(j)){
                i ++;
                j --;
            }else {
                return false;
            }
        }
        return true;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

思路二：动态规划（区间DP）

状态表示：f[i][j]：s表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是f[i][j]为true，否则为false。

状态计算：当s[i] == s[j]时，f[i][j] = f[i + 1][j - 1]

初始化：

• 当区间长度为1时，也就是只有一个字符，那肯定是回文子串
• 当区间长度为2时，若前后两个字符相等，则说明改子串也是回文串

Code

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
       
        boolean[][] f = new boolean[n + 10][n + 10];
        int res = 0;
        // 初始化：当子串是一个字符时(子串长度为1)
        for(int i = 0; i < n; i ++){
            f[i][i] = true;
            res ++;
        }
        // 初始化：当子串长度为2时
        for(int i = 0; i < n - 1; i ++){
            if(s.charAt(i) == s.charAt(i + 1)){
                res ++;
                f[i][i + 1] = true;
            }
        }
        // 从区间长度为3 开始枚举子串
        for(int len = 3; len <= n; len ++){// 区间长度
            for(int i = 0; i + len <= n; i ++){// 左端点
                int j = i + len - 1;
                if(s.charAt(i) == s.charAt(j)){
                    f[i][j] = f[i + 1][j - 1];
                    if(f[i][j]){// 子所以能成为回文串，那是因为我的区间长度是从小到大枚举的
                        res ++;
                    }

                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

Code

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
       
        boolean[][] f = new boolean[n + 10][n + 10];
        int res = 0;
        // 初始化：当子串是一个字符时(子串长度为1)
        for(int i = 0; i < n; i ++){
            f[i][i] = true;
            res ++;
        }

        // 从区间长度为2 开始枚举子串
        for(int len = 2; len <= n; len ++){// 区间长度
            for(int i = 0; i + len <= n; i ++){// 左端点
                int j = i + len - 1;
                if(s.charAt(i) == s.charAt(j)){
                    if(j - i + 1 < 3){// 长度为2时
                        f[i][j] = true;
                    }else{
                        f[i][j] = f[i + 1][j - 1];
                    }
                    // 当满足回文串就计数
                    if(f[i][j]){
                        res ++;
                    }
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

41.最长回文子串

题目链接：5. 最长回文子串 - 力扣（LeetCode）

和上一题基本一样，只不过本题求的是最长的回文串，而不是长度。

修改上一题的代码，竟然超时了：

Code

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int begin = 0;
        int maxlen = 0;
        for(int i = 0; i < n; i ++){
            for(int j = i; j < n; j ++){
                String tmp = s.substring(i, j + 1);
                if(is_huiwen(tmp)){
                    if(j - i + 1 > maxlen){
                        begin = i;
                        maxlen = j - i + 1;
                    }
                }
            }
        }
        return s.substring(begin, begin + maxlen);
    }
    public boolean is_huiwen(String s){
        int i = 0;
        int j = s.length() - 1;
        while(i < j){
            if(s.charAt(i) == s.charAt(j)){
                i ++;
                j --;
            }else {
                return false;
            }
        }
        return true;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

思路二：中心扩散法

我们从前往后枚举，以i为中心，向着左右两端逐渐扩散（双指针），判断是否能够成回文串。这样子扩散的话回文串就分为奇数长度和偶数长度两种回文串，我们取最大者即可。

Code

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";
        for(int i = 0; i < n; i ++){
            // 偶数长度的情况 aabb
            int l = i, r = l + 1;
            while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                l --;
                r ++;
            }
            if(r - l - 1 > res.length()) res = s.substring(l + 1, r);

            // 奇数的情况 abcba
            l = i - 1; r = i + 1;
            while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                l --;
                r ++;
            }
            if(r - l - 1 > res.length()) res = s.substring(l + 1, r);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

动态规划：

Code

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();

        boolean[][] f = new boolean[n + 10][n + 10];
        // 初始化：当子串是一个字符时(子串长度为1)
        for(int i = 0; i < n; i ++){
            f[i][i] = true;
        }
        // 从区间长度为2 开始枚举子串
        int begin = 0;
        int maxlen = 1;// 从一开始 当字符串长度为2时要用 如 ac
        for(int len = 2; len <= n; len ++){// 区间长度
            for(int i = 0; i + len <= n; i ++){// 左端点
                int j = i + len - 1;
                if(s.charAt(i) == s.charAt(j)){
                    if(j - i < 3){// 区间长度为2
                        f[i][j] = true;
                    }else {
                        f[i][j] = f[i + 1][j - 1];
                    }
                }
    // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
                if(f[i][j] && j - i + 1 > maxlen){
                    maxlen = j - i + 1;
                    begin = i;
                }

            }
        }
        System.out.println(begin + " " + maxlen);
        return s.substring(begin, begin + maxlen);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

41.最长回文子序列

题目链接：516. 最长回文子序列 - 力扣（LeetCode）

状态表示：f[i][j]：所有s[i....j]的回文子序列的集合

属性：Max长度

状态计算：判断s[i] 与 s[j]是否相等

• s[i] == s[j]：f[i][j] = f[i + 1][j - 1] + 2
• s[i] != s[j]：f[i][j] = max(f[i][j - 1], f[i + 1][j])
  • 删除s[i]：f[i + 1][j]
  • 删除s[j]：f[i][j - 1]
  • 都删除，包含在了上面的两种情况，忽略

注意：f[i][j]的状态由f[i + 1][j - 1]、f[i + 1][j]、f[i][j - 1]转移而来，再求f[i][j]前这些状态必须要是作为已知条件才可以！

可以画个矩阵草图，就可以发现，这些状态有的是在(i, j)后面才出现的，为了求得这些状态我们就要从后往前遍历（逆序遍历）！

Code

class Solution {
    // s[i] == s[j] : f[i][j] = f[i + 1][j - 1] + 2;
    // s[i] != s[j] : f[i][j] = max(f[i + 1][j], f[i][j - 1])
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        s = " " + s;
        int[][] f = new int[n + 10][n + 10];
        for(int i = 0; i <= n; i ++) f[i][i] = 1;

        for(int i = n; i >= 1; i --){// 从后往前遍历
            for(int j = i + 1; j <= n; j ++){
                if(s.charAt(i) == s.charAt(j)){
                    f[i][j] = f[i + 1][j - 1] + 2;
                }else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[1][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21