[数据结构与算法] 【力扣刷题】Day31—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【力扣刷题】Day31——DP专题 -> 正文阅读

[数据结构与算法]【力扣刷题】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

for(int i = 0; i < n; i ++) f[i] = 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;
    }
}

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];
    }
}

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];
    }
}

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;

最后的结果：所有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;
    }
}

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

另一种状态表示的写法：

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

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

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

状态表示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;
    }
}

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

在区间[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;
     }
}

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]);
    }
}

编辑距离

题目链接：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];
    }

}

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

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

我们可以求两个串的最长公共子序列，然后判断最长公共子序列的长度是否等于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;
    }
}

另一种思考方式：我们采用编辑距离的思考方式来实现（本身它的状态转移方程就跟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;
    }
}

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];
    }
}

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

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];
    }
}

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];
    }
}

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

思路二：动态规划（区间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;
    }
}

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

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

思路二：中心扩散法

我们从前往后枚举，以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;
    }
}

动态规划：

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);
    }
}

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];
    }
}