最长回文子序列

不念不忘少年蓝@ 2022-10-29 12:23 165阅读 0赞

/** * 最长回文子序列 * 输入一个字符串s，请找出s中最长回文子序列的长度 * dp[i][j]是子串s[i...j]中的最长回文子序列的长度 */
    public class Solution10 { 
    
        public static void main(String[] args) { 
            String s = "aecda";
            System.out.println(maxLength(s));
        }
    
        static int maxLength(String s) { 
            int[][] dp = new int[s.length()][s.length()];
            for (int i = 0; i < s.length(); i++) { 
                for (int j = 0; j < s.length(); j++) { 
                    dp[i][j] = 0;
                }
            }
            for (int k = 0; k < s.length(); k++) { 
                dp[k][k] = 1;
            }
            for (int i = s.length()-2; i >= 0; i--) { 
                for (int j = i + 1; j < s.length(); 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][s.length()-1];
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 [回文系列] 回文数、最长回文子串、最长回文子序列

1、验证回文数 LintCode：[https://www.lintcode.com/problem/palindrome-number/description][h...

雨点打透心脏的1/2处/ 2024年04月18日 16:59/ 0 赞/ 84 阅读

相关 LeetCode-516. 最长回文子序列

动态规划本题思路动态规划题目来源 [516. 最长回文子序列][516.] 本题思路回文子串是要连续的，回文子序列可不是连

我就是我/ 2024年03月24日 13:00/ 0 赞/ 39 阅读

相关 516.最长回文子序列

516.最长回文子序列题干分析解题思路 1. 确定dp数组（dp table）以及下标的含义 2. 确定递推公式

水深无声/ 2024年03月01日 08:13/ 0 赞/ 47 阅读

相关 leetcode516 最长回文子序列

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "b

系统管理员/ 2023年06月19日 02:16/ 0 赞/ 173 阅读

相关最长回文子序列

/ 最长回文子序列输入一个字符串s，请找出s中最长回文子序列的长度 dp[i][j]是子串s[i...j]中的最长回文子序列的长度 / public c

不念不忘少年蓝@/ 2022年10月29日 12:23/ 0 赞/ 166 阅读

相关 leetcode516最长回文子序列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

爱被打了一巴掌/ 2022年09月04日 09:47/ 0 赞/ 169 阅读

相关 516 最长回文子序列（区间dp）

1. 问题描述：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

我就是我/ 2022年08月30日 04:05/ 0 赞/ 173 阅读

相关【LeetCode】516. 最长回文子序列

题目链接：[https://leetcode-cn.com/problems/longest-palindromic-subsequence/description/][htt

柔光的暖阳◎/ 2022年05月03日 00:56/ 0 赞/ 153 阅读

相关最长回文子序列（不连续）可输出回文序列

string LCS(string str1,string str2)//str2是str1的逆序 { string fin=str1;

柔情只为你懂/ 2022年02月24日 11:12/ 0 赞/ 188 阅读

相关 Leetcode516. 最长回文子序列

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "b

系统管理员/ 2022年01月05日 08:07/ 0 赞/ 222 阅读