Leetcode.516.最长回文子序列

最长回文子序列

  • 前言
  • 一、算法思想
  • 二、源代码
  • 三、找规律改进算法
    • 1、想法
    • 2、源代码
  • 四、总结

前言

算法打卡,第一次碰到动态规划,通过学习掌握动态规划。
动态规划通俗的讲就是找规律。将一个大而复杂的问题通过其规律来拆解成一个一个同步的问题。
规划:找规律拆解问题
动态:同步动态更新需要的数值
个人理解,比较抽象,下面有实际例子。

一、算法思想

找规律:
一个最短的回文左右加两个相同的字符,又变成一个长度加2的回文。或者说一个长度大于2的回文去掉首尾仍然是一个回文。这里的仍然就是规律。所以我们只需要从最短序列开始找回文。
动态更新:
一环套一环,用短的更新长的序列,而每次序列加1,通过上一次的序列所求的回文长度去更新新序列的每一段(每一段取短序列也是依此递增加1)
对于字符串"bbbab",更新这个数组看起来如下:
10000
21000
32100
32110
43311
第一次取序列长度为1,然后依次递增。这是外层循环
内部也从长度为2开始取(前后字符比较),然后依次递增,但不大于外存所取的长度。这是内层循环
内层的更新就是根据上层的数或者当前层靠后一个数来更新(因为前后字符串可能相等也可能不等,两种情况更新情况不同)

二、源代码

public int longestPalindromeSubseq(String s) {
     
        int len = s.length();
        int[][] dp = new int[len][len];//1.申请数组来存更新值
        for(int i = 0;i < len;i++){
     
            dp[i][i] = 1;
            for(int j = i - 1;j >= 0;j--){
     
            //2.两种情况的更新方式,根据规律来更新的
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i-1][j+1] + 2;
                else
                    dp[i][j] = Math.max(dp[i][j+1],dp[i-1][j]);
            }
        }
        //3.双重循环为了用短序列回文数更新长序列,最终更新到最长序列。
        return dp[len-1][0];
    }

三、找规律改进算法

1、想法

从上面的规律发现,我们需要用上一次的数来更新当前序列的数,也就是dp[i-1][j]或者dp[i-1][j+1],其它情况都是dp[i][?],所以我们用temp1,temp2两个临时变量来把上一个数存起,这样就可以安全的从后面向前面更新(覆盖)数据。
对于字符串"bbbab",更新这个数组看起来如下:
10000
21000
32100
32110
43311

2、源代码

public int longestPalindromeSubseq(String s) {
     
        int len = s.length();
        int[] dp = new int[len];
        for(int i = 0;i < len;i++){
     
            int temp1 = dp[i],temp2;
            dp[i] = 1;
            for(int j = i - 1;j >= 0;j--){
     
                temp2 = dp[j];
                if(s.charAt(i) == s.charAt(j)) {
     
                    dp[j] = temp1 + 2;
                }
                else
                    dp[j] = Math.max(dp[j+1],temp2);
                temp1 = temp2;
            }

        }
        return dp[0];
    }

四、总结

  1. 动态规划==找到一环套一环的规律。
  2. 时间复杂度:两个算法都是O(n2)
  3. 空间复杂度:第一个O(n2),它用了一个二维数组。第二个O(n),只用了一个一维数组加两个临时变量。
  4. 动态规划四步
    1)状态
    dp[i][j]表示i到截断的字符串回文的最长序列
    2)状态转移方程
    两种情况
if(s.charAt(i) == s.charAt(j))
    dp[i][j] = dp[i-1][j+1] + 2;
else
    dp[i][j] = Math.max(dp[i][j+1],dp[i-1][j]);
//或者:
dp[i][j] = s.charAt(i) == s.charAt(j) ? dp[i-1][j+1] + 2 : Math.max(dp[i][j+1],dp[i-1][j]);
//注:这样更利于CPU的运算效率。

3)初始化
dp[i][i] = 1;表示一个字母最长回文为1。
4)结果
dp[s.length() - 1][0]

你可能感兴趣的