每日leetcode第0070天 0409. Longest Palindromic Subsequence

今天做的是动态规划的题目,最长回文子序列。

我们要区分清楚子序列和子串,子串是要连续的,子序列只需要按原串的顺序即可。

这道题定义的二维数组是从i到j的最长回文子序列。

初始化的时候,我们要知道任何一个单独的字母都是长度为1的回文序列。

所以初始化lps[i][i] = 1;

接下来就是要进行状态转移了,这里我们要分两种情况。

1.i和j的两个字母是相同的字母,那么他们就是内部那一串的最长长度+2了。

2.两个字母不同,那么它俩我们就认为最多用一个要么左边那个要么右边那个,就是取[i+1][j]和[i][j-1]中大的那一个。

搞清楚后,我们要知道遍历的顺序,要从最下面那行开始算。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。