高校网站建设管理制度,怎么找到外贸公司采购,长沙做个网站多少钱,酒店网络营销推广案例文章目录 day57学习内容一、回文子串1.1、动态规划五部曲1.1.1、 确定dp数组#xff08;dp table#xff09;以及下标的含义1.1.2、确定递推公式1.1.3、 dp数组如何初始化1.1.4、确定遍历顺序1.1.5、输出结果 1.2、代码 二、最长的回文子串2.1、动态规划五部曲2.1.1、 确定dp… 文章目录 day57学习内容一、回文子串1.1、动态规划五部曲1.1.1、 确定dp数组dp table以及下标的含义1.1.2、确定递推公式1.1.3、 dp数组如何初始化1.1.4、确定遍历顺序1.1.5、输出结果 1.2、代码 二、最长的回文子串2.1、动态规划五部曲2.1.1、 确定dp数组dp table以及下标的含义2.1.2、确定递推公式2.1.3、 dp数组如何初始化2.1.4、确定遍历顺序2.1.5、输出结果 2.2、代码2.2.1、如何理解dp[i][j] dp[i 1][j - 1] 2; 总结1.感想2.思维导图 day57学习内容 day57主要内容 2个字符串的删除操作最长的回文子串 声明 本文思路和文字引用自《代码随想录》 一、回文子串
647.原题链接
1.1、动态规划五部曲
1.1.1、 确定dp数组dp table以及下标的含义
dp[i][j]是一个布尔值用于表示子字符串s[i...j]是否为回文。如果dp[i][j]为true则说明从索引i到j的子字符串是回文。
1.1.2、确定递推公式
基本情况 当i j时s[i...j]是单个字符显然是回文。当j i 1时如果s[i] s[j]则s[i...j]是由两个相同字符组成的回文。 递推关系 对于j i 1如果s[i] s[j]且dp[i1][j-1]为true即去除两端字符后的子字符串是回文则s[i...j]也是回文。
或者这么理解 在每次循环中会判断当前子字符串s[i...j]是否是回文
基本条件 (if (chars[i] chars[j])): 如果两端的字符相同进一步判断是否构成回文。 情况一和情况二 (if (j - i 1)): 如果i和j相同或者是相邻的位置即子字符串长度为1或2则这个子字符串是回文。情况三 (else if (dp[i 1][j - 1])): 如果不是上述情况但内部的子字符串s[i1...j-1]是回文由dp[i1][j-1]为true表示那么s[i...j]也是回文。
在每个条件成立时都会将dp[i][j]设置为true并将结果计数器result加一。
1.1.3、 dp数组如何初始化
初始状态由于所有的布尔值在Java中默认初始化为falsedp数组最开始全部为false。在遍历过程中我们会根据回文的条件来更新特定的dp[i][j]为true。
1.1.4、确定遍历顺序
外层循环从字符串的末尾开始向前遍历即i从len-1降至0。这样做确保当我们检查dp[i][j]是否为回文时dp[i1][j-1]即内部子字符串的值已经被确定。内层循环从i开始向字符串的末尾遍历即j从i增至len-1。这种方式可以确保每次检查的都是从位置i开始的所有可能的子字符串。
1.1.5、输出结果
结果result是一个整数用于计数整个字符串中所有的回文子串。每次当找到一个回文即dp[i][j]被设置为true时result就增加1。最终方法返回result值这就是字符串s中所有回文子串的数量。
1.2、代码
class Solution {public int countSubstrings(String s) {// 将输入字符串转换为字符数组便于单个字符访问char[] chars s.toCharArray();// 获取字符串的长度int len chars.length;// 初始化一个二维布尔数组来存储回文状态dp[i][j]为true表示s[i...j]是回文boolean[][] dp new boolean[len][len];// 用于计数回文子串的数量int result 0;// 外层循环从字符串的末尾开始向前遍历for (int i len - 1; i 0; i--) {// 内层循环从当前字符位置向字符串的末尾遍历for (int j i; j len; j) {// 检查两端的字符是否相同if (chars[i] chars[j]) {// 检查是否是最基本的回文条件单个字符或两个相同的字符if (j - i 1) {// 如果是标记为回文并计数dp[i][j] true;result;} else if (dp[i 1][j - 1]) { // 检查内部子字符串是否是回文// 如果内部子字符串也是回文那么整个字符串也是回文dp[i][j] true;result;}}}}// 返回回文子串的总数return result;}
}二、最长的回文子串
516.原题链接
2.1、动态规划五部曲
2.1.1、 确定dp数组dp table以及下标的含义
dp[i][j]表示字符串中从索引i到索引j的子字符串的最长回文子序列的长度。
2.1.2、确定递推公式 字符相等的情况 当s[i]等于s[j]时意味着我们可以在子字符串s[i1...j-1]的最长回文子序列的两端分别添加s[i]和s[j]。因为两端字符相等且已经构成了s[i1...j-1]的回文子序列的两端这会形成一个新的更长的回文子序列。这就是为什么递推公式是dp[i][j] dp[i1][j-1] 2。 字符不等的情况 当s[i]不等于s[j]时意味着s[i]和s[j]不能同时被用来形成一个更长的回文子序列。在这种情况下我们有两个选择 忽略字符s[i]考虑子字符串s[i1...j]。忽略字符s[j]考虑子字符串s[i...j-1]。 因此我们需要比较这两个子问题的解选取其中较大的一个递推公式为dp[i][j] max(dp[i1][j], dp[i][j-1])。
递推公式的实现
在初始化时每个单字符子字符串自身是一个长度为1的回文子序列所以dp[i][i] 1。对于每一对i和j其中i j根据上述规则更新dp[i][j]。
示例 考虑字符串“cbbd”
如果i0和j3且s[0] ! s[3]则考虑dp[1][3]和dp[0][2]取最大值。
没有废话的版本
当字符相等时如果s[i]和s[j]相等这意味着我们可以在内部子字符串s[i1...j-1]的最长回文子序列的基础上加上这两个相等的字符形成更长的回文子序列。因此递推公式是dp[i][j] dp[i1][j-1] 2。当字符不相等时如果s[i]和s[j]不相等那么最长的回文子序列要么不包含s[i]要么不包含s[j]。因此递推公式是dp[i][j] max(dp[i1][j], dp[i][j-1])。
2.1.3、 dp数组如何初始化
数组定义定义了一个二维数组dp其维度为len1 x len1其中len是输入字符串s的长度。这个数组用来存储所有子字符串的最长回文子序列的长度。基本回文每个单字符都是一个回文子序列所以在遍历开始前将对角线上的dp[i][i]初始化为1即dp[i][i] 1。这表示每个由单个字符组成的子字符串都至少有一个字符的回文子序列。
2.1.4、确定遍历顺序
外层循环i从字符串的最后一个字符开始递减到第一个字符。这种从后向前的遍历方式是为了保证当处理dp[i][j]时dp[i1][j-1]已经被计算符合动态规划的依赖顺序。内层循环j从i1开始递增到字符串的末尾。这样可以确保我们总是在处理长度大于1的子字符串并且当i固定时我们从较短的子字符串逐渐处理到较长的子字符串。
2.1.5、输出结果
输出结果整个字符串的最长回文子序列长度存储在dp[0][len-1]中其中len是字符串s的总长度。这个值在所有计算完成后直接返回即为所求的整个字符串的最长回文子序列的长度。
2.2、代码
public class Solution {public int longestPalindromeSubseq(String s) {// 获取输入字符串的长度int len s.length();// 创建一个二维数组dp用于存储子字符串的最长回文子序列长度int[][] dp new int[len][len];// 从字符串的最后一个字符开始反向遍历确保计算dp[i][j]时dp[i1][j-1]已经被计算过for (int i len - 1; i 0; i--) {// 单个字符总是回文子序列长度为1dp[i][i] 1;// 从i1开始向右遍历计算所有可能的子字符串for (int j i 1; j len; j) {// 如果两端的字符相同可以在dp[i1][j-1]的基础上两端各加一个字符if (s.charAt(i) s.charAt(j)) {dp[i][j] dp[i 1][j - 1] 2;} else {// 如果两端字符不同取不包含当前字符i或字符j的子字符串的最长回文子序列的最大值dp[i][j] Math.max(dp[i 1][j], dp[i][j - 1]);}}}// dp[0][len-1]存储了整个字符串的最长回文子序列长度return dp[0][len - 1];}
}2.2.1、如何理解dp[i][j] dp[i 1][j - 1] 2;
当我们查看字符串的一个子序列假设它的起始索引是 i结束索引是 j我们需要决定s[i...j]的最长回文子序列是什么。在递推公式dp[i][j] dp[i1][j-1] 2;中 dp[i1][j-1]: 这部分代表子字符串s[i1...j-1]的最长回文子序列的长度。即当我们去掉当前考虑的子字符串两端的字符后内部子字符串的最长回文子序列长度。 加2的逻辑如果s[i]和s[j]字符相同这意味着我们可以在s[i1...j-1]的最长回文子序列的基础上在两端各加上字符s[i]和s[j]从而形成一个更长的回文子序列。因此整个子字符串s[i...j]的最长回文子序列长度会是内部子字符串s[i1...j-1]的长度加2加上两端相同的字符。
举个例子
假设有字符串 “cbbd”我们想知道子字符串 “bb” 的最长回文子序列。 初始化 dp[i][i] 对于所有 i 都设为 1因为每个单独的字符都是长度为1的回文子序列。 填充动态规划表 当我们检查 “bb”即 i1, j2时因为两端的字符相同s[1] 和 s[2] 都是 ‘b’。查看去掉两端的子字符串 “b[11…2-1]”即 dp[2][1]但这是无效的区间其基本长度为0在实际初始化中可能直接被视为基础情况。由于两端字符相同我们可以在这个基础上前后各添加一个 ‘b’因此dp[1][2] 的值应更新为 0 2 2。
总结
1.感想
动态规划了终于结束了。。
2.思维导图 本文思路引用自代码随想录感谢代码随想录作者。
