算法训练营第六十天(延长12天添加图论) | LeetCode 647 回文子串、LeetCode 516 最长回文子序列
LeetCode 67 回文子串
思路很简单,每一个dp[i]等于dp[i-1]加上当前字符向前直到0各个长度字符串回文串个数即可
代码如下:
class Solution { public boolean isValid(String s) { int l = 0, r = s.length() - 1; while (l = 0; j--) { String ss = s.substring(j, i+1); if (isValid(ss)) dp[i]++; } } return dp[s.length() - 1]; } }
LeetCode 516 最长回文子序列
这题要在上一题基础上稍微转换下思路。
原本是从前往后循环内从后往前统计回文字符串数目,这题是从中间往两边,看两边分别接触到的第一个字符是否相等。
如果相等就都放入,并且dp[i][j]等于dp[i+1][j-1]+2,否则dp[i][j]取dp[i+1][j]、dp[i][j-1]、dp[i][j]中最大值即可。这就是这道题的递推逻辑了。
初始化方式是在i==j时要初始化为1。或者将dp[i][i]初始化为1也行
从递归公式中,可以看出,dp[i][j] 依赖于 dp[i + 1][j - 1] ,dp[i + 1][j] 和 dp[i][j - 1],如图:
所以遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的。
代码如下:
public class Solution { public int longestPalindromeSubseq(String s) { int len = s.length(); int[][] dp = new int[len + 1][len + 1]; for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏 dp[i][i] = 1; // 初始化 for (int j = i + 1; j
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。