C++刷leetcode（516. 最长回文子序列）【动态规划】

糖逗

题目描述：

1. 
   
2. 给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
   
3. 
   
4. 示例 1:
   
5. 输入:
   
6. 
   
7. "bbbab"
   
8. 输出:
   
9. 
   
10. 4
    
11. 一个可能的最长回文子序列为 "bbbb"。
    
12. 
    
13. 示例 2:
    
14. 输入:
    
15. 
    
16. "cbbd"
    
17. 输出:
    
18. 
    
19. 2
    
20. 一个可能的最长回文子序列为 "bb"。

复制代码

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

复制代码

注意事项：
1.参考链接：https://leetcode-cn.com/problems ... su-by-a380922457-3/
2.注意for(int i = len - 1; i >= 0; i--)这一行代码

糖逗

继续学习动态规划