当前位置：首页 > news >正文

代码随想录训练营第五十七天|647. 回文子串、516.最长回文子序列

news 2025/8/23 15:39:56

647. 回文子串

题目链接/文章讲解/视频讲解：代码随想录

1.代码展示

//647.回文子串
int countSubstrings(string s) {//step1 构建dp数组，明确dp数组的含义，dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));//step2 构建状态转移方程//当s[i] != s[j]时，此时必定不为回文子串//当s[i] == s[j]时，有三种情况//情况一：i = j，此时就是本身，因此必定为回文子串//情况二：i + 1 = j，此时就如aa的形式，因此也是回文子串//情况三：j > i + 1，此时当dp[i + 1][j - 1]为回文字串时，dp[i][j]才是回文子串//step3 初始化dp数组，都为false//step4 开始遍历int nResult = 0;for (int i = s.size() - 1; i >= 0; i++) {for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) {nResult++;dp[i][j] = true;}else if (dp[i + 1][j - 1]){nResult++;dp[i][j] = true;}}}}return nResult;
}

2.本题小节

思考：本题的重点在于对于dp[i][j]的理解，dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串。构建状态转移方程，当s[i] != s[j]时，此时必定不为回文子串；当s[i] == s[j]时，有三种情况
，情况一，i = j，此时就是本身，因此必定为回文子串，情况二，i + 1 = j，此时就如aa的形式，因此也是回文子串，情况三：j > i + 1，此时当dp[i + 1][j - 1]为回文字串时，dp[i][j]才是回文子串；初始化都为false，最后注意遍历顺序，先下后上，先左后右。

基本思路：注意理解dp[i][j]的含义，按照代码的思路来即可。

516.最长回文子序列

题目链接/文章讲解/视频讲解：代码随想录

1.代码展示

//516.最长回文子序列
int longestPalindromeSubseq(string s) {//step1 构建dp数组，dp[i][j]的含义是在[i,j]下标的范围内s的最长回文子序列vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));//step2 状态转移方程//当s[i] == s[j]，dp[i][j] = dp[i + 1][j - 1] + 2，//不等时，有两种情况，说明同时加入s[i],s[j]不能满足情况，分别加入s[i]和s[j]试试//则dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])//step3 初始化for (int i = 0; i < s.size(); i++) {dp[i][i] = 1;}//step4 开始遍历for (int i = s.size() - 1; i >= 0; i++) {for (int j = i + 1; j < s.size(); j++) {if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;}else {dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);}}}return dp[0][s.size() - 1];
}

2.本题小节

思考：明确dp数组的含义。dp[i][j]的含义是在[i,j]下标的范围内s的最长回文子序列。状态转移方程，当s[i] == s[j]，dp[i][j] = dp[i + 1][j - 1] + 2，不等时，有两种情况，说明同时加入s[i],s[j]不能满足情况，分别加入s[i]和s[j]试试，则dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])，初始化时对角线都为1，根据dp数组可以得。遍历时先下后上，先左后右。

基本思路：注意dp数组的含义，按照动态规划步骤来。