数据机构与算法|Leetcode.516.最长回文子序列动态规划|算法|字符串|java|le

【数据机构与算法|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]; }

四、总结

动态规划==找到一环套一环的规律。

时间复杂度：两个算法都是O(n2)

空间复杂度：第一个O(n2)，它用了一个二维数组。第二个O(n)，只用了一个一维数组加两个临时变量。

动态规划四步
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的运算效率。