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

news/2024/3/29 6:55:24/文章来源:https://blog.csdn.net/qq_54773252/article/details/127446652

文章目录

    • 七、子序列问题(线性DP and 区间DP)
      • 1、子序列(不连续)
        • 29.最长递增子序列(LIS)
        • 30. 最长公共子序列 (LCS)
        • 31.不相交的线
      • 2、子序列(连续)
        • 32. 最长连续递增序列
        • 33.最长重复子数组(TODO)
        • 34. 最大子序和
      • 3、编辑距离
        • 最短编辑距离
        • 编辑距离
        • 35.判断子序列
        • 36.不同的子序列(计数)
        • 37. 不同的子序列II(计数)
        • 38. 两个字符串的删除操作
        • 39.编辑距离
      • 4、回文(区间DP)
        • 40.回文子串
        • 41.最长回文子串
        • 41.最长回文子序列


上一篇文章:【力扣刷题】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] != jf[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 ++){// 偶数长度的情况 aabbint 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);// 奇数的情况 abcbal = 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时要用 如 acfor(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){// 区间长度为2f[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];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_404426.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言中的指针

一。什么是指针&#xff1f; 在计算机科学中&#xff0c;指针&#xff08;Pointer&#xff09;是编程语言中的一个对象&#xff0c;利用地址&#xff0c;它的值直接指向&#xff08;points to&#xff09;存在电脑存储器中另一个地方的值。由于通过地址能找到所需的变量单元&a…

一棋盘的麦子

14天阅读挑战赛 有一个古老的传说&#xff0c;一位国王的女儿不幸落水&#xff0c;水中有很多鳄鱼&#xff0c;国王情急之下下令&#xff1a; 来&#xff0c;就把女儿嫁给他。”很多人纷纷退让&#xff0c;一个勇敢的小伙子挺身而出&#xff0c;冒着生命危险把公 一看是个穷小子…

Java程序员快速掌握前端知识

Java程序员是一个需要终身学习的岗位&#xff0c;加之技术更新迭代越来越快&#xff0c;程序员们不得不坚持提升自己&#xff0c;上班可能接触到新事物&#xff0c;下班也要抓紧时间钻研&#xff0c;才能不被时代淘汰。 前端技术&#xff0c;Java程序员可以不精通&#xff0c;…

新手如何自学python?

对于初学者来说&#xff0c;视频教程相比于书籍更加直观有效&#xff0c;可以先看视频进行学习&#xff0c;然后再看书进行深刻学习~下面就给你分享下教程以及书籍~ 网站 1. 网易公开课 https://open.163.com/ 2. 腾讯课堂 https://ke.qq.com/ 3. 中国大学慕课 https://www.…

xxl-job反序列化漏洞分析复现

01 影响范围 Xxl-Job<2.1.2&#xff0c;需要利用Hessian触发。 02 环境搭建 下载地址&#xff1a;https://github.com/xuxueli/xxl-job/releases 修改配置文件 xxl-job-2.0.1/xxl-job-admin/src/main/resources/application.properties 修改数据库信息&#xff0c;以及…

动手写数据库:实现记录管理

在数据库中&#xff0c;数据以”记录“作为一个单元来存储&#xff0c;例如一个表的“一行”就对应一条记录。假设我们有一个表叫STUDENT&#xff0c;其中有name, age, sex, class等字段&#xff0c;那么一条记录的信息就由这四个字段对应的信息合成。一条记录如何存储并不是一…

FFmpeg入门详解之110:RTSP协议讲解

RTSP亲手搭建直播点播 测试工具&#xff1a;VLC 数据源&#xff1a; 文件或本地摄像头 测试功能&#xff1a;RTSP直播点播 播放地址&#xff1a;rtsp://127.0.0.1:8554/rtspa001 服务端&#xff1a;推流 客户端&#xff1a;拉流 RTSP&#xff08;Real Time Streaming Pro…

Windows定时截屏、后台自动截屏工具,带有密码保护功能 —— 定时执行专家

目录 一、软件简介 二、使用教程 1、软件下载 2、软件的安装方法 3、无察觉自动截屏&#xff08;例如&#xff1a;间隔每 10分钟&#xff0c;执行 1次&#xff09; 一、软件简介 《定时执行专家》是一款制作精良、功能强大、简单易用、毫秒级精度、专业级的定时任务执行软…

Windows Server安全日志与系统事件变更审计

了解用户何时变更计算机内部时钟上的时间和日期。如果系统时间已变更&#xff0c;记录的事件将反映此新时间&#xff0c;而不是事件发生的实际时间。对系统时间不正确的变更可对应用程序造成严重破坏。 您可在Windows 2003 / 2008 / 2012计算机的安全日志中找到有价值信息&…

SpringBoot——可真是迅速又便捷

刚工作那会用的还是tomcat、springMVC、hibernate、mybatis、html、jsp……搭个项目可真是麻烦&#xff0c;各种复杂的结构还得打个war包配置web.xml&#xff0c;启动tomcat……后来也没做网站开发了&#xff0c;最近又看了看springboot&#xff0c;比之前那种开发web项目简单多…

测试人生 | 转行测试开发,4年4“跳”年薪涨3倍,我的目标是星辰大海(附大厂面经)!

编者按&#xff1a;本文来自霍格沃兹测试学院优秀学员TesterC&#xff0c;**从运营岗位转行外包测试&#xff0c;再到测试开发&#xff0c;从待业在家到4年4“跳”进入 BAT 大厂&#xff0c;年薪涨了3倍&#xff01;**他是如何完成如此励志的华丽转身的&#xff1f; 应学院的邀…

C++5-explicit、const的用法、mutable、常成员函数构成重载、在主函数中修改m_i的值

一、explicit的使用 explicit作用&#xff1a; 明确确定构造函数只能构造对象 代码示例&#xff1a; class A { public:A(int i 0):m_i(i){cout<<"A"<<i<<endl;}//构造函数可以用作类型转换&#xff0c;将int转换成类对象//explicit A(int i …

网络原理 --- 传输层Ⅰ UDP协议

文章目录网络原理传输层UDP 协议总结网络原理 介绍TCP/IP协议中每一层里面的核心内容~ 应用层传输层网络层数据链路层物理层 传输层 传输层主要负责端到端之间的传输,重点关注的是起点和终点 核心的协议有两个: UDP: 无连接 ,不可靠传输,面向数据报,全双工TCP : 有连接,可…

1024程序员节来了,

在中国“硅谷”西三旗&#xff0c;高精尖人才聚集地&#xff0c;一个砖头扔下来&#xff0c;砸中的10个人中&#xff0c;有7个是程序员 如今&#xff0c;程序员已发展成社会的主流职业&#xff0c;有多主流呢&#xff1f; 街头的王大妈李大爷都在讨论&#xff1a; “我儿子程…

vite+vue3+ts项目搭建之集成qiankun让其成为子应用模板(vite+vue3+ts+qiankun项目)

前言 以下操作&#xff0c;是续接之前 第四步 ——即&#xff1a;vitevue3tspiniaelement-plus项目已完成搭建好&#xff0c;可以直接业务开发了 主应用技术栈&#xff1a;vue2webpackjs 集成qiankun(微前端) 1、安装vite-plugin-qiankun npm install vite-plugin-qiankun2、…

在Eclipse 中使用 Maven 创建雅加达 EE 应用程序

在本教程中&#xff0c;我将指导大家如何在 Eclipse 中创建新的雅加达 EE 应用程序支持 Maven。 首先&#xff0c;在 Eclipse 中&#xff0c;转到“文件”&#xff0c;选择“新建”&#xff0c;然后选择“Maven 项目”&#xff1a; 要使用 Maven 创建雅加达 EE 项目&#xff0…

操作系统闲谈01——IO多路复用

IO多路复用 同步异步IO问题 select&#xff0c;poll&#xff0c;epoll都是IO多路复用的机制。I/O多路复用就通过一种机制&#xff0c;可以监视多个描述符&#xff0c;一旦某个描述符就绪&#xff08;一般是读就绪或者写就绪&#xff09;&#xff0c;能够通知程序进行相应的读…

贴片电阻的读数方法

贴片电阻图 今天讲一下贴片电阻的阻值、精度与贴片电阻丝印之间细微的关系。 大家经常见到的贴片电阻上的丝印有纯数字、数字与R组合、数字与除R之外的字母组合的&#xff0c;但大家知不知道这样的标注与贴片电阻的i精度相关&#xff1f;同一个阻值因为精度不同&#xff0c;标…

【Git】Git基本配置和常用命令

&#x1f4ad;&#x1f4ad; ✨&#xff1a; git基本配置和命令   &#x1f49f;&#xff1a;东非不开森的主页   &#x1f49c;&#xff1a;学习的过程就是不断接触错误&#xff0c;不断提升自己&#xff0c;冲鸭&#x1f49c;&#x1f49c;   &#x1f338;: 如有错误或不…

从前端到全栈

你会学到什么&#xff1f; 掌握 Node.js 开发必备基础知识&#xff1b;理解 HTTP 协议核心原理与实践&#xff1b;基于 Node.js 实现自己的工程脚手架;从 0 打造在线绘图 Web 应用。 作者介绍 月影&#xff0c;字节跳动 ByteTech 负责人&#xff0c;资深 JavaScript 程序员&am…