代码随想录算法练习营第42天 | 第九章 动态规划13

---

本日记录

---

647. 回文子串

Leetcode链接

1. class Solution {
2. public:
3.     int countSubstrings(string s) {
4.         vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
5.         int result = 0;
6.         for (int i = s.size() - 1; i >= 0; i--) {
7.             for (int j = i; j < s.size(); j++) {
8.                 if (s[i] == s[j]) {
9.                     if (j - i <= 1) {
10.                         result++;
11.                         dp[i][j] = true;
12.                     } else if (dp[i + 1][j - 1]) {
13.                         result++;
14.                         dp[i][j] = true;
15.                     }
16.                 }
17.             }
18.         }
19.         return result;
20.     }
21. };

复制代码

516.最长回文子序列

1. class Solution {
2. public:
3.     int longestPalindromeSubseq(string s) {
4.         vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
5.         for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
6.         for (int i = s.size() - 1; i >= 0; i--) {
7.             for (int j = i + 1; j < s.size(); j++) {
8.                 if (s[i] == s[j]) {
9.                     dp[i][j] = dp[i + 1][j - 1] + 2;
10.                 } else {
11.                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
12.                 }
13.             }
14.         }
15.         return dp[0][s.size() - 1];
16.     }
17. };

复制代码

---

总结


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。