最长回文子序列

不念不忘少年蓝@ 2022-10-29 12:23 170阅读 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 条评论，170人围观）

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

相关阅读

相关 516.最长回文子序列

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

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

相关 516. 最长回文子序列（动态规划）

516. 最长回文子序列题目解题思路代码题目给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长

秒速五厘米/ 2023年10月05日 19:27/ 0 赞/ 4 阅读

相关 leetcode516 最长回文子序列

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

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

相关最长回文子序列

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

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

相关 leetcode516最长回文子序列

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

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

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

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

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

相关最长回文子串

include <iostream> include <vector> include <string> include <algori

淩亂°似流年/ 2022年06月17日 06:53/ 0 赞/ 292 阅读

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

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

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

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

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

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

相关 Leetcode516. 最长回文子序列

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

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