动态规划最后一天(回文串)

目录

647. 回文子串

看到题目的第一想法               

看到代码随想录之后的想法

自己实现过程中遇到的困难(看代码)

516.最长回文子序列

看到题目的第一想法               

看到代码随想录之后的想法

自己实现过程中遇到的困难(看代码)

---

647. 回文子串

力扣题目链接(opens new window)

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

• 输入："abc"
• 输出：3
• 解释：三个回文子串: "a", "b", "c"

示例 2：

• 输入："aaa"
• 输出：6
• 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：输入的字符串长度不会超过 1000 。

看到题目的第一想法
               

         按照回溯来做，没做出来，没法用回溯来写

        使用暴力可以解

        使用dp 将数目记录，但是递推公式不好计算     

        

看到代码随想录之后的想法

        用动态规划，若i==j 则看i和j之间是否是回文串，如果是回文则dp[i][j]也是回文

        (选中两个单词的字符，若相同看中间是否是回文)

        确定dp数组和每个下标的含义

        dp[i][j],看i和j之间是否是回文串

        

        

        确定递推公式

               若s[i]==s[j] 则有三种情况

                若i==j 则dp[i][j]=true

                若i=j-1 则dp[i][j]=true

                若i>j-1，则dp[i][j] = dp[i+1][j-1]（看i，j中间的是否是回文串）

        dp数组初始化

        初始化都为false，相当于遍历时若为回文则改为true    

        确定遍历顺序

        dp[i][j] 依赖于 dp[i+1][j-1] 则可以从下往上，从左往右进行遍历

        举例推导dp数组           

        打印dp数组

        遍历时记录true的个数，返回总数，就是回文子串的个数了

自己实现过程中遇到的困难(看代码)

        回溯没写出来

        第一时间想一下暴力

        回文串记得通过[i,j]中间的来进行判断

        

class Solution {public int countSubstrings(String s) {//我的思路是记录回文子串数目，其中dp数组是不太好推测的//卡哥的思路是，利用dp[i][j]二维数组，看[i，j] 是否是回文子串//若为回文子串则为true ，若不为则为false//若 s[i] s[j]相等，那么我们可以看[i+1][j-1] 是否为回文子串,若为回文，则dp[i][j]也为回文(相当于包在里面)//确定dp数组和下标的含义// dp[i][j] 看[i,j]是否为回文子串，若是则为true，否则为false//确定递推公式// 若s[i]=s[j] 有三种情况   1 i==j 则直接为true//                         2 i==j-1 则直接为true//                         3 i<j-1 则需要判断 若dp[i+1][j-1]==true 则dp[i][j]为true//dp数组初始化//全都为false ，先默认都不为回文子串，然后再一个个改成回文子串//确定遍历顺序//dp[i][j]依赖于dp[i+1][j-1]，则从下往上，从前往后//举例推导dp数组int result = 0;boolean[][] dp = new boolean[s.length()][s.length()];for(int i=s.length()-1;i>=0;i--){for(int j=i;j<s.length();j++){if(s.charAt(i)==s.charAt(j)){if(i==j||i==j-1||dp[i+1][j-1]==true){dp[i][j] = true;result++;}}}}return result;}
}//我的想法，用回溯？判断是否回文，是则加入result中//回溯算法三要素//回溯函数的参数和返回值//字符串以及startIndex//回溯函数的终止条件//若字符串到最后则返回//回溯函数的执行逻辑//若startIndex到i为回文串则加入到结果集中//正着读和倒着读一样的字符串//dp[i][j] 遍历到[i-1,j-1]里面回文子串的数目，// 确定递推公式// 若[i-1,j-1]为回文子串，则dp[i][j] = Math.max(dp[i-1][j]+1,dp[i][j-1]+1)// 若[i-1,j-1]不为回文子串,dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);// dp数组初始化// 都为0// 确定遍历顺序// 从上往下从左至右/*int[][] dp = new int[s.length()+1][s.length()+1];for(int i=1;i<=s.length();i++){for(int j=i;j<=s.length();j++){if(isValid(s,i-1,j-1)){dp[i][j] = Math.max(dp[i-1][j]+1,dp[i][j-1]+1);}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}/return dp[s.length()][s.length()];//backTracking(s,0);//return resultPath.size();}boolean isValid(String s,int i,int j){//判断是否是回文while(i<j){if(s.charAt(i)!=s.charAt(j)){return false;}i++;j--;}return true;}/*void backTracking(String s,int startIndex){if(startIndex==s.length()){return ;}for(int i=startIndex;i<s.length();i++){if(isValid(s,startIndex,i)){String sub = s.substring(startIndex,i+1);if(isValid(sub)){resultPath.add(sub);}}else{continue;}backTracking(s,startIndex+1);   }}boolean isValid(String s){//判断是否是回文int i=0;int j=s.length()-1;while(i<j){if(s.charAt(i)!=s.charAt(j)){return false;}i++;j--;}return true;}*/
//}

                   

516.最长回文子序列

力扣题目链接(opens new window)给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

看到题目的第一想法
               

        dp[i][j]记录所有和i相等的j 的个数当成回文串

        写出来发现不符合题意，比如说aabaa也是回文串，但是a的个数为4 ，串长度为5

        求的是串的长度

        

看到代码随想录之后的想法

        用动态规划，若i==j 则看i和j之间回文串的最大长度

        (选中两个单词，看中间回文串的最大长度)

        确定dp数组和每个下标的含义

        dp[i][j],看i和j之间回文串的最大长度

        

        

        确定递推公式

               若s[i]==s[j] 则dp[i][j] = dp[i+1][j-1]+2 

                若s[i]!=s[j] 看选中其中一个字符的最长回文是多少，则

                                dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);

        dp数组初始化

        当i==j时，一定时回文，全都初始化为1    

        确定遍历顺序

        dp[i][j] 依赖于 dp[i+1][j-1] 则可以从下往上，从左往右进行遍历

        举例推导dp数组           

        打印dp数组

        遍历时记录true的个数，返回总数，就是回文子串的个数了

自己实现过程中遇到的困难(看代码)

       理解一下回文的含义

        回文串记得通过[i,j]中间的来进行判断，相等时不要忘了dp[i+1][j-1] +2 

        做的时候忘了+2了

        

class Solution {public int longestPalindromeSubseq(String s) {//卡哥的思路//dp[i][j] 记录[i~j]的最长的回文子序列//确定递推公式//若s[i]==s[j] 则看两者间最长的回文子序列是多少 dp[i][j] = dp[i+1][j-1]+2 加了两个字符，所以加2//若s[i]!=s[j] 则看选中s[i] 于选中s[j]的两个序列中，最长的回文子序列是多少(两者的最大值)// dp[i][j] = max(dp[i+1][j],dp[i][j-1])//确定遍历顺序//由于dp依赖于dp[i+1][j-1]则dp[i][j]遍历顺序为由下往上，从左往右//dp数组初始化//当i==j时一定是回文，所以dp[i][i]=1int[][] dp = new int[s.length()][s.length()];for(int i=0;i<s.length();i++){dp[i][i]=1;}for(int i=s.length()-2;i>=0;i--){for(int j=i+1;j<s.length();j++){if(s.charAt(i)==s.charAt(j)){dp[i][j] = dp[i+1][j-1]+2;}else{dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);}}}//返回0~length-1的最大值return dp[0][s.length()-1];/*//我的思路：和之前那道题思路一样？ 想着所有和i相等的都是回文，其实是错误的比如bbabb 回文长度为5 我为4//若i==j dp[i][j] = dp[i][j-1]+1 //若i!=j dp[i][j] = dp[i][j-1]//确定dp的参数和下标的含义//i-1~j-1之间以i开头最长的子序列的长度//确定递推公式//若s[i-1]==s[j-1] dp[i][j] = dp[i][j-1]+1//若s[i-1]!=s[j-1] dp[i][j] = dp[i][j-1]//dp数组初始化//默认为0//确定遍历顺序//从上往下，从左至右//举例推导dp数组int[][] dp = new int[s.length()+1][s.length()+1];int max = 0;for(int i=1;i<s.length()+1;i++){for(int j=i;j<s.length()+1;j++){if(s.charAt(i-1)==s.charAt(j-1)){dp[i][j] = dp[i][j-1]+1;if(dp[i][j]>max){max = dp[i][j];}}else{dp[i][j] = dp[i][j-1];}}}return max;*/}
}