二刷代码随想录训练营Day 46|647. 回文子串、516.最长回文子序列、动态规划 ...

1.回文子串

   代码随想录 (programmercarl.com)
  视频：动态规划，字符串性子决定了DP数组的定义 | LeetCode：647.回文子串_哔哩哔哩_bilibili
  代码：

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.                         dp[i][j] = true;
11.                         result++;
12.                     }else if(dp[i + 1][j - 1] == true){
13.                         dp[i][j] = true;
14.                         result++;
15.                     }
16.                 }
17.             }
18.         }
19.         return result;
20.     }
21. };

复制代码

 note：
为了实现递推，拥有这种递推关系，最好是如果判断两头的元素相等，且两头内的字符串本身就是回文子串，就证实现在的子串也是回文子串，从而实现了递推关系。
dp数组的寄义：dp[j]表示下标为[i,j]的字符串是否为回文子串
递推公式：

1. if(s[i] == s[j]){
2.      if(j - i <= 1){
3.         dp[i][j] = true;
4.         result++;
5.     }else if(dp[i + 1][j - 1] == true){
6.         dp[i][j] = true;
7.         result++;
8.     }
9. }

复制代码

dp数组的初始化：为了不影响计算，全部初始化为false
遍历顺序：根据递推公式，可知，我们要从下往上，从左往右遍历

2.最长回文子序列

   代码随想录 (programmercarl.com)  视频：动态规划再显神通，LeetCode：516.最长回文子序列_哔哩哔哩_bilibili
  代码：

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++){
6.             dp[i][i] = 1;
7.         }
8.         for(int i = s.size() - 1; i >= 0; i--){
9.             for(int j = i + 1; j < s.size(); j++){
10.                 if(s[i] == s[j]){
11.                     dp[i][j] = dp[i + 1][j - 1] + 2;
12.                 }else{
13.                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
14.                 }
15.             }
16.         }
17.         return dp[0][s.size() - 1];
18.     }
19. };

复制代码

 note：
dp数组的寄义：下标为[i,j]的最长回文子序列的长度为dp[j]
递推公式：

1. if(s[i] == s[j]){
2.     dp[i][j] = dp[i + 1][j - 1] + 2;
3. }else{
4.     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
5. }

复制代码

注意子序列不必一连！
dp数组的初始化：将下标为[i,i]的元素全部初始化为1
遍历顺序：
 根据递推公式，可知，我们要从下往上，从左往右遍历

3.动态规划总结

   代码随想录 (programmercarl.com)

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