• 周二. 10 月 8th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

516. 最长回文子序列 力扣(中等) 区间dp,不会做

admin

11 月 28, 2021

516. 最长回文子序列

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。

题解:https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/gong-shui-san-xie-qu-jian-dp-qiu-jie-zui-h2ya/

https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-dv83q/

代码:

class Solution {
public:
    int longestPalindromeSubseq(string s) {
    // dp[i][j]:表示第i个字符到第j个字符之间,最长的回文子序列长度
    int dp[1005][1005];
    int l=s.length();
    memset(dp,0,sizeof(dp));
    for(int i=0;i<l;i++) dp[i][i]=1;
    for(int i=l-1;i>=0;i--)   // for(int i=0;i<l;i++)  因为看递推公式,需要借助下层结果,所以反着循环
      for(int j=i+1;j<l;j++)
      {
             if(i+1==j)
             {
                 if(s[i]==s[j]) dp[i][j]=2;
                     else dp[i][j]=1;
                continue;
             } 
            if (s[i]==s[j]) {dp[i][j]=dp[i+1][j-1]+2; continue;}
            if (s[i]!=s[j]) {dp[i][j]=max(dp[i+1][j],dp[i][j-1]); continue;}
      }
      return dp[0][l-1];
    }
};

发表回复