算法笔记|Day40动态规划XIII
算法笔记|Day40动态规划XIII
- ☆☆☆☆☆leetcode 647. 回文子串
- 题目分析
- 代码
- ☆☆☆☆☆leetcode 516.最长回文子序列
- 题目分析
- 代码
☆☆☆☆☆leetcode 647. 回文子串
题目链接：leetcode 647. 回文子串
题目分析
1.dp数组含义：dp[i][j]表示表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串；
2.递推公式：if(s.charAt(i)==s.charAt(j))：if(j-i<=1)dp[i][j]=true;else if(dp[i+1][j-1])dp[i][j]=true;（若i位置元素与j位置元素不同，一定不是回文子串，无需操作；只需要考虑i位置元素与j位置元素相同时，即s.charAt(i)==s.charAt(j)。在此基础上，若下标i与j相同或差为1，是回文子串；若下标i与j相差大于1，看i到j区间是不是回文子串就看i+1与j-1区间；如果是回文子串，res加一）；
3.初始化：所有dp[i][j]=false；
4.遍历顺序：i从大到小，j从小到大，而且j大于等于i，j从i开始。
代码
class Solution {public int countSubstrings(String s) {boolean dp[][]=new boolean[s.length()][s.length()];int res=0;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(j-i<=1){dp[i][j]=true;res++; }else if(dp[i+1][j-1]){dp[i][j]=true;res++; } }}}return res;}
}
☆☆☆☆☆leetcode 516.最长回文子序列
题目链接：leetcode 516.最长回文子序列
题目分析
1.dp数组含义：dp[i][j]表示字符串s在[i, j]范围内最长的回文子序列的长度；
2.递推公式：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])（若i位置元素与j位置元素相同，回文子序列长度在dp[i+1][j-1]基础上加二；若i位置元素与j位置元素不同时，取[i+1, j]与[i, j-1]两个区间最长回温子序列的最大值）；
3.初始化：所有dp[i][i]=1；
4.遍历顺序：i从大到小，j从小到大，而且j大于等于i，j从i+1开始。
代码
class Solution {public int longestPalindromeSubseq(String s) {int dp[][]=new int[s.length()][s.length()];for(int i=0;i<s.length();i++)dp[i][i]=1;for(int i=s.length()-1;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]);}}}return dp[0][s.length()-1];}
}