ToB企服应用市场:ToB评测及商务社交产业平台

标题: 算法打卡：第九章 动态规划part13 [打印本页]
作者: 花瓣小跑    时间: 2024-9-19 21:41
标题: 算法打卡：第九章 动态规划part13
今日劳绩：回文子串，最长回文子序列

1. 回文子串

标题链接：647. - 力扣（LeetCode）
思路：
（1）dp数组的界说不再是标题的要求，而是二维的，下标 i 和 j 表示字符串对应下标的子串是不是回文串。再使用变量记录回文子串的个数
（2）初始化全为0
（3）如果当前两个字符相等，判定长度是否为0或1，满足要求则都是回文子串；如果长度大于1，那么下标向中间聚拢，如果仍然是回文子串，记录个数。
（4）遍历次序：依据递推公式，需要下标向中间聚拢也就是左下角的值推出当前值，所以需要从上到下从左到右遍历。
方法：
  1. class Solution {
  2.     public int countSubstrings(String s) {
  3.         int len=s.length();
  4.         int result=0;
  6.         // 字符串中从 i 到 j 的子串是不是回文串
  7.         boolean[][] dp=new boolean[len][len];
  9.         // 初始化
  10.         for (int i=0;i<len;i++){
  11.             for (int j=0;j<len;j++){
  12.                 dp[i][j]=false;
  13.             }
  14.         }
  16.         // 从底向上，从左到右
  17.         for (int i=len-1;i>=0;i--){
  18.             for (int j=i;j<len;j++){
  19.                 if (s.charAt(i)==s.charAt(j)){
  20.                     if (j-i<=1){
  21.                         dp[i][j]=true;
  22.                         result++;
  23.                     }else {
  24.                         dp[i][j]=dp[i+1][j-1];  // 向中间靠拢
  25.                         if (dp[i][j]==true){
  26.                             result++;
  27.                         }
  28.                     }
  29.                 }
  30.             }
  31.         }
  33.         return result;
  34.     }
  35. }
复制代码
2. 最长回文子序列

标题链接：516. - 力扣（LeetCode）
思路：
（1）dp数组表示 i 和 j 下标范围内的最长回文子序列长度
（2）初始化：递推公式不包罗长度为1的回文子串，所以二维数组的对角线元素全为1
（3）递推公式：如果 i 和 j 下标上的字符相等，那么回文子序列的长度在内层子串的基础上加2；如果不相等，则取分别加上左边的字符和右边的字符中的最大值。
（4）遍历次序：从递推公式可以看出来，当前位置依靠于左，左下，下的元素值，所以是从下到上，从左到右遍历。
方法：
  1. class Solution {
  2.     public int longestPalindromeSubseq(String s) {
  3.         int len=s.length();
  5.         // 设置为len+1，初始化较为简单
  6.         int[][] dp=new int[len+1][len+1];
  8.         for (int i=len-1;i>=0;i--){
  9.             dp[i][i]=1;
  10.             for (int j=i+1;j<len;j++){
  11.                 if (s.charAt(i)==s.charAt(j)){
  12.                     dp[i][j]=dp[i+1][j-1]+2;
  13.                 }else {
  14.                     dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
  15.                 }
  16.             }
  17.         }
  19.         return dp[0][len-1];
  20.     }
  21. }
复制代码
总结：
（1）子序列和子串的区别在于，子序列可以删除元素，如果可以删除的环境不止一个就需要取此中的最大值。
（2）如果不能确定遍历次序，可以根据递推公式，分析dp数组中当前位置的值由哪些方向的值推导出来。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4