ppt链接网站怎么做,wordpress谷歌字体库,信息网站大全,东莞市公司网站建设怎么样Day51 动态规划第十三天
LeetCode 647. 回文子串
dp数组的含义#xff1a;i到j的子串是否是回文的#xff0c;是的话dp[i][j]1 递推公式#xff1a;if(s[i]s[j]) i j 一个元素 是回文的 |i-j|1 两个元素 是回文的 j-i1 判断dp[i1][j-1] 初始化#xff1a;全部初始化成…Day51 动态规划第十三天
LeetCode 647. 回文子串
dp数组的含义i到j的子串是否是回文的是的话dp[i][j]1 递推公式if(s[i]s[j]) i j 一个元素 是回文的 |i-j|1 两个元素 是回文的 j-i1 判断dp[i1][j-1] 初始化全部初始化成false 遍历顺序从左到右 从下往上
class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(),vectorbool(s.size(),false));int res0;for(int is.size()-1;i0;i--){for(int ji;js.size();j){if(s[i]s[j]){if(j-i1){res;dp[i][j]true;}else if(dp[i1][j-1]){res;dp[i][j]true;}}}}return res;}
};LeetCode 516.最长回文子串
dp数组的含义[i,j]的回文子串的长度 递推公式if(s[i]s[j]) dp[i][j]dp[i1][j-1]2; else dp[i][j]max(dp[i][j-1],dp[i1][j]) 初始化dp[i][i]1 其余无所谓初始化为0 遍历顺序从左到右 从下往上
class Solution {
public:int longestPalindromeSubseq(string s) {vectorvectorint dp(s.size(),vectorint(s.size(),0));for(int i0;is.size();i) dp[i][i]1;for(int is.size()-1;i0;i--){for(int ji1;js.size();j){if(s[i]s[j])dp[i][j]dp[i1][j-1]2;elsedp[i][j]max(dp[i1][j],dp[i][j-1]);}}return dp[0][s.size()-1];}
};动态规划结束啦
