【代码随想录训练营】Day57-动态规划
代码随想录训练营 Day57
今日任务
647.回文子串
516.最长回文子序列
动态规划总结
语言:Java
647. 回文子串
链接:https://leetcode.cn/problems/palindromic-substrings/
class Solution {
public int countSubstrings(String s) {
int[][] dp = new int[s.length()][s.length()];
//dp[i][j]: 从i~j的子串是否为回文子串
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(i == j){
dp[i][j] = 1;
}
else if(Math.abs(j - i) == 1){
dp[i][j] = 1;
}
else if(j - i > 1){
dp[i][j] = dp[i + 1][j - 1];
}
}
res += dp[i][j];
}
}
return res;
}
};
/*
a b b a c
a 1 0 0 1 0
b 1 1 0 0
b 1 0 0
a 1 0
c 1
*/
516. 最长回文子序列
链接:https://leetcode.cn/problems/longest-palindromic-subsequence/
代码随想录
class Solution {
public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
//i~j位的最长子串长度
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++){
//如果相等,就说明i位和j位都可以加入到当前最长回文子序列中
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i + 1][j - 1] + 2;
}
//如果不相等,就寻找加入i位或j位后最长回文子序列更长的
else{
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][s.length() - 1];
}
}
/*
b b b a b
b 1 2 3 3 4
b 1 2 2 3
b 1 1 2
a 1 1
b 1
*/
/*
c b b d
c 1 1 2 2
b 1 2 2
b 1 1
d 1
*/