小游戏网页版在线玩,纯静态网站页面优化,wordpress数据库主机填什么,wordpress留言群发# 力扣第47天— 第647题、第516题 文章目录 一、第647题--回文子串二、第516题--最长回文子序列 一、第647题–回文子串
逻辑梳理清楚了#xff0c;就还行。没有想象中那么难。注意遍历顺序#xff0c;i从大到小。
class Solution {
public:int countSubstrings(string …# 力扣第47天— 第647题、第516题 文章目录 一、第647题--回文子串二、第516题--最长回文子序列 一、第647题–回文子串
逻辑梳理清楚了就还行。没有想象中那么难。注意遍历顺序i从大到小。
class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false));int result 0;for (int i s.size()-1; i0; i--){for (int j i; j s.size()-1; j){if(s[i] s[j]) {if (j-i 1) {dp[i][j] true;result;}else {dp[i][j] dp[i1][j-1];if (dp[i][j]) result;}}}}return result;}
};二、第516题–最长回文子序列
还可以吧跟上一题差不多。遍历顺序一样但是要注意j的遍历起点为i1因为递归的时候涉及到i1会导致越界。递推公式要想一想但是难度不大。
class Solution {
public:int longestPalindromeSubseq(string s) {vectorvectorint dp(s.size(), vectorint(s.size(), 0));for(int i 0; is.size(); i) dp[i][i] 1;for(int i s.size()-1; i0; i--){for (int j i1; j s.size(); j){// cout dp[i][j] -;if(s[i] s[j]) dp[i][j] dp[i1][j-1] 2;else dp[i][j] max(dp[i1][j], dp[i][j-1]);}}return dp[0][s.size()-1];}
};
