栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

最长回文子序列

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

最长回文子序列

动态规划思想的不同实现
public class solution9 {
    //最长回文子序列


    

    

    
    


    

   

   public int  longestPalindromeSubSeq(String s){
       //获取长度
       int len = s.length();
       //创建一个二维数组,行和列是一样长的
       int [][] dp=new int[len][len];
       for (int i = len-1; i >=0 ; i--) {
     
           dp[i][i]=1;//初始化
    
           for (int j = i+1; 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]);
                   //不相等长度始终为1
                   }
           }
       }

       
       
       //最终返回的始终是最外层回文串,最外层的值又是里面的层包围的串决定的。所以降低了比较次数,用空间换时间。
       return dp[0][len-1];
   }


    public static void main(String[] args) {
        String s="abbcccd";
        solution9 solution9=new solution9();
        int i = solution9.longestPalindromeSubSeq(s);
        System.out.println(i);
    }

下面是for循环执行过程,可以通过他来建立二维表,理解本题

public class testij {
    public static void main(String[] args) {
        int len=5;
             //变i来比较  相当于倒着比较
        for (int i = len-1; i >=0 ; i--) {
            System.out.println("输出i:"+i);
            //j保持不变   j维持恒定
            for (int j = i + 1; j < len; j++) {
                System.out.println("输出j:"+j);
            }
        }
        int max = Math.max(1, 1);
        System.out.println("Max:"+max);
    }
}

输出i:4
输出i:3
输出j:4
输出i:2
输出j:3
输出j:4
输出i:1
输出j:2
输出j:3
输出j:4
输出i:0
输出j:1
输出j:2
输出j:3
输出j:4
Max:1

总结
  • 如果一个子串的两头的字符不相等,那么就不是回文
  • 如果一个子串的两头相等 我们需要看去掉了相等字符的子串是不是两头相等
  • 两头相等时,整体是不是回文由中间那部分决定,这就是动态规划 他的状态被前一状态影响
  • i字符串的开始 j字符串的结束 dp[i][j]表示原字符串 s[i][j]子串
  • 转态转移方程 子串的回文性质决定了整体的回文性质 if(s[i]==s[j]) dp[i+1][j-1]决定dp[i][j]
  • dp[i+1][j-1]表示去掉头尾字符的子串
  • 边界条件 既然是下标访问一定要考虑下标是否有效 i+1和j-1构成的区间是不是存在 j-i<3没有意义
  • 每一步计算都尽可能用到了前面计算的结果 这也是典型的以空间换时间的思想
  • 考虑初始化 初始化的时候 单个字符肯定是回文串 dp[i][i]=1
  • 输出:比较两个字符相等就记录下长度 存储在二维数组
  • 动态规划就是在填写一张二维表格
  • 根据i j画出二维表 i和j的关系是i小于等于j 我们只需要填写表的上半部分 记录了子串的所有状态*/
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/962541.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号