LeetCode 516. Longest Palindromic Subsequence (Java版; Meidum)

淩亂°似流年 2023-05-28 14:21 32阅读 0赞

### [welcome to my blog][] ###

## LeetCode 516. Longest Palindromic Subsequence (Java版; Meidum) ##

#### 题目描述 ####

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
    
    Example 1:
    Input:
    
    "bbbab"
    Output:
    4
    One possible longest palindromic subsequence is "bbbb".
    Example 2:
    Input:
    
    "cbbd"
    Output:
    2
    One possible longest palindromic subsequence is "bb".

#### 第一次做, 动态规划 核心:1) dp\[i\]\[j\]表示\[i,j\]上的最长回文子串 2) 根据递推公式中的依赖关系可知, 需要从下往上, 从左往右遍历 ####

class Solution { 
        public int longestPalindromeSubseq(String s) { 
            /* dp[i][j]表示s[i,j]上的最长回文子序列长度 i相当于左边界, j相当于右边界 dp[i][j] = dp[i+1][j-1] + (s[i]==s[j]?1:0) */
            int n = s.length();
            int[][] dp = new int[n][n];
            for (int i = 0; i < n; i++) { 
                dp[i][i] = 1;
            }
            for (int i = n - 1; i >= 0; i--) { 
                for (int j = i + 1; j < n; j++) { 
                    if (s.charAt(i) == s.charAt(j)) { 
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else { 
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[0][n - 1];
    
        }
    }

[welcome to my blog]: https://littlehaes.com

发表评论取消回复

表情：

评论列表（有 0 条评论，32人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 409. Longest Palindrome (Java版; Easy)

[welcome to my blog][] LeetCode 409. Longest Palindrome (Java版; Easy) 题目描述

末蓝、/ 2023年07月17日 02:47/ 0 赞/ 36 阅读

相关 LeetCode 516. Longest Palindromic Subsequence (Java版; Meidum)

[welcome to my blog][] LeetCode 516. Longest Palindromic Subsequence (Java版; Meidum)

淩亂°似流年/ 2023年05月28日 14:21/ 0 赞/ 33 阅读

相关【Leetcode】409. Longest Palindrome

思路：用一个Set存储前面出现过的字母，遍历整个字符串，如果Set中没有出现过，则加入Set，否则移除该字符并加二计数，最后再判断是否Set为空，若是则计数加一。

「爱情、让人受尽委屈。」/ 2022年09月30日 15:51/ 0 赞/ 71 阅读

相关 leetcode 516. Longest Palindromic Subsequence | 516. 最长回文子序列（递归 -＞傻缓存 -＞DP）

题目 [https://leetcode.com/problems/longest-palindromic-subsequence/][https_leetcode.co

客官°小女子只卖身不卖艺/ 2022年09月12日 01:48/ 0 赞/ 87 阅读

相关 LeetCode-Longest Palindromic subString(java)

在各大面试公司中回文的String型和Int型题目有很多，是非常常见的算法题，今天我就解决此类问题的方法进行汇总。 1.笨方法我们只需要将所给的字符串进行遍历就

清疚/ 2022年08月09日 06:16/ 0 赞/ 25 阅读

相关 leetcode Longest Palindromic Substring

题目 Given a string S, find the longest palindromic substring in S. You may assume that

本是古典何须时尚/ 2022年08月05日 00:51/ 0 赞/ 170 阅读

相关 LeetCode：Longest Palindromic Substring

第五题是求字符串里的最大回文子串，回文串（Palindromic Substring）就是例如”aba”，“abba”这种，网上有很多使用解决方法，比如使用动归，kmp的变种等

谁践踏了优雅/ 2022年07月12日 07:43/ 0 赞/ 129 阅读

相关 leetcode 516. Longest Palindromic Subsequence 最长回文子序列 + DP动态规划

Given a string s, find the longest palindromic subsequence’s length in s. You may assume

谁借莪１个温暖的怀抱￠/ 2022年06月03日 03:10/ 0 赞/ 197 阅读

相关 LeetCode-Longest Palindromic Subsequence

文章目录 Longest Palindromic Subsequence 题目描述思路分析 C++实现 Sc

太过爱你忘了你带给我的痛/ 2022年03月20日 04:46/ 0 赞/ 133 阅读

相关 LeetCode-Longest Palindromic Substring

文章目录 LeetCode-Longest Palindromic Substring 题目描述思路分析 C++实现

- 日理万妓/ 2022年03月20日 03:31/ 0 赞/ 161 阅读