代码随想录算法训练营第五十七天 | 647. 回文子串、516. 最长回文子序...

发布网友发布时间：2024-08-16 22:25

共1个回答

热心网友时间：2024-08-21 20:40

在代码随想录算法训练营的第五十七天，我们探讨了两个相关的回文问题：647. 回文子串和516. 最长回文子序列。首先，647题要求统计字符串s中回文子串的数量，回文子串是指正读和反读都相同的子串，每个子串的开始和结束位置都不同。暴力解法的时间复杂度是O(n^3)，但通过动态规划可以优化为O(n^2)，定义一位二维布尔数组dp，判断区间[i,j]是否为回文，递推公式根据子串[i+1, j-1]的回文性来确定。

对于516题，目标是找到字符串s中最长的回文子序列长度。与回文子串不同，回文子序列允许不连续字符。同样使用动态规划，定义dp[i][j]为s[i,j]范围内最长回文子序列的长度。递推公式根据s[i]和s[j]的比较来调整，如果相同则长度加2，不同则取左右两个子序列长度的最大值。

在初始化dp数组时，特别注意边界情况，如单个字符的回文子序列长度为1，其他情况初始为0。遍历顺序是先确定下边界再确定上边界，保证所有依赖的dp值已计算。举例说明dp数组的变化可以帮助理解和编写代码。