LeetCode算法题

小灰灰 2024-03-31 08:43 76阅读 0赞

#### 题目1.最长回文字符串![68be524a32c44daa8406a0589231efd3.png][] ####

这题为动态规划（主要是找到状态转移方程）的子序列问题

解题思路：

状态表示：dp\[i\]\[j\]表示字符串的闭区间\[i,j\]内是否为回文字符串

状态转移方程：当s\[i\]==s\[j\]的时候

情况1：i==j；dp\[i\]\[j\]为回文字符串；

情况2：j-i==1；dp\[i\]\[j\]为回文字符串；

情况3：下标：i 与 j相差大于1的时候，例如cabac，此时s\[i\]与s\[j\]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp\[i + 1\]\[j - 1\]是否为回文字符串。

求解时i，j的顺序

![3225c1f1b75d4f648818876806df7d3f.png][]

如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp\[i + 1\]\[j - 1\]，也就是根据不确定是不是回文的区间\[i+1,j-1\]，来判断了\[i,j\]是不是回文，那结果一定是不对的。

所以一定要从下到上，从左到右遍历，这样保证dp\[i + 1\]\[j - 1\]都是经过计算的。

提交代码：

char * longestPalindrome(char * s){
        int i,j,left=0,right=0,dp[1001][1001]={0},max=0,k=0;
        char *p=malloc(sizeof(char)*1001);
        int len=strlen(s);
        for(i=len-1;i>=0;i--)
        {
            for(j=i;j<len;j++)
            {
                if(s[i]==s[j])
                {
                    if(j==i)
                       dp[i][j]=1;
                    if(j-i==1)
                       dp[i][j]=1;
                    if(j-i>1)
                    {
                        if(dp[i+1][j-1]==1)
                        {
                            dp[i][j]=1;
                        }
                    }
                }
                if(dp[i][j]==1)
                {
                   if(j-i+1>max)
                   {
                       max=j-i+1;
                       left=i;
                       right=j;
                   }
                }
            }
        }
        for(i=left;i<=right;i++)
        {
            p[k++]=s[i];
        }
        p[k]='\0';
        return p;
    }

[68be524a32c44daa8406a0589231efd3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/107b42324c494b3aa70097b078e7ddf5.png
[3225c1f1b75d4f648818876806df7d3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/59b3f0c9a65543b794d49afea646fa8e.png