口腔网站设计图,建立什么船籍港,wordpress 显示相册,郑州网站建设找智巢题意理解#xff1a; 给你一个字符串 s #xff0c;找出其中最长的回文子序列#xff0c;并返回该序列的长度。 子序列定义为#xff1a;不改变剩余字符顺序的情况下#xff0c;删除某些字符或者不删除任何字符形成的一个序列。 回文理解为元素对称的字串#xff0c;这里… 题意理解 给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。 子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。 回文理解为元素对称的字串这里求字符串中最长的对称字串的长度。 使用动态规划的思路来进行解题。 解题思路 1定义dp数组 dp[i][j]表示从i到j的字串中最长回文序列的长度 2递推公式 当且仅当s[i]s[j] dp[i][j]dp[i1][j-1]2 否则dp[i][j]Max(dp[i1][j],dp[i][j-1],dp[i1][j-1]) (3) 初始化一个元素是回文所以dp[i][j],ij时值为1 (4由于dp[i][j]受dp[i1][j-1]影响所以遍历顺序从左到右从上到下 最后返回dp[0][s.size-1] 1.动态规划解题 public int longestPalindromeSubseq(String s) {int[][] dpnew int[s.length()][s.length()];for(int i0;is.length();i){Arrays.fill(dp[i],0);dp[i][i]1;}for(int is.length()-1;i0;i--){for(int ji1;js.length();j){if(s.charAt(i)s.charAt(j)){dp[i][j]dp[i1][j-1]2;}else{dp[i][j]Math.max(Math.max(dp[i][j-1],dp[i1][j]),dp[i1][j-1]);}}}return dp[0][s.length()-1];}
2.复杂度分析 时间复杂度O(n^2) 空间复杂度O(n^2)
