問題描述:
給出一個字元串str,傳回這個字元串的最長回文子序列長度;比如:str = "a123b321c"
最長回文子序列是123b321,傳回長度是7
解決方案:從暴力遞歸到動态規劃演變,三種方案如下
1、暴力遞歸:
public class NanDaoPalindromeSum {
public static void main(String[] args) {
String s = "a123b321c";
System.out.println(palindrome1(s));
}
/**
* 暴力遞歸
* @param s
* @return
*/
private static int palindrome1(String s) {
if(s == null || s.length() == 0){
return 0;
}
char[] str = s.toCharArray();
return p1(str,0,str.length - 1);
}
private static int p1(char[] str, int L, int R) {
if(L == R){
return 1;
}
if(L == R - 1){
return str[L] == str[R] ? 2:1;//相等是2,不等是1
}
int p1 = p1(str,L + 1,R - 1);
int p2 = p1(str,L,R - 1);
int p3 = p1(str,L + 1,R);
int p4 = str[L] == str[R] ? (2 + p1(str,L + 1,R - 1)) : 0;
// System.out.println("p1:"+p1+";P2:"+p2+";P3:"+p3+";P4:"+p4);
return Math.max(Math.max(p1,p2),Math.max(p4,p3));//傳回最大值
}
}
2、暴力遞歸到動态規劃的過渡階段:
2.1、圖示分析:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL90TQPFTR6JGaS1mYoVjMMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL1ATOwIjNwITM5IjNwEjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
給出的字元串 String s = "a123b321c"; 長度為 9 ;行是L,列是R,L<=R;當L==R時,對角線指派1,挨着對角線問号(?)指派為1或2(R 和R+1相等為2),右上角為最終傳回值
2.2、核心代碼:
public class NanDaoPalindromeSum {
public static void main(String[] args) {
String s = "a123b321c";
System.out.println(palindrome2(s));
}
/**
* 暴力遞歸到動态規劃的過渡階段
* @param s
* @return
*/
private static int palindrome2(String s) {
if(s == null || s.length() == 0){
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[][] dp = new int[N][N];
dp[N - 1][N - 1] = 1;
for(int i = 1;i < N - 1;i++){
dp[i][i] = 1;
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;//相等是2,不等是1
}
for(int L = N - 3;L >= 0;L--){
for(int R = L + 2;R < N;R++){
int p1 = dp[L + 1][R - 1];
int p2 = dp[L][R - 1];
int p3 = dp[L + 1][R];
int p4 = str[L] == str[R] ? (2 + dp[L + 1][R - 1]) : 0;
dp[L][R] = Math.max(Math.max(p1,p2),Math.max(p3,p4));
}
}
return dp[0][N - 1];
}
}
3、标準的動态規劃方案:
3.1、繼續分析上圖:某個格子位置是其左邊和下邊取最大值得到的,即6位置是從5和3位置中取最大值得到的,肯定不是其左下(2位置)的值,是以可以繼續優化代碼;
3.2、核心代碼如下:
public class NanDaoPalindromeSum {
public static void main(String[] args) {
String s = "a123b321c";
System.out.println(palindrome3(s));
}
/**
* 動态規劃
* @param s
* @return
*/
private static int palindrome3(String s) {
if(s == null || s.length() == 0){
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[][] dp = new int[N][N];
dp[N - 1][N - 1] = 1;
for(int i = 0;i < N - 1;i++){
dp[i][i] = 1;//對角線指派為1
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;//對角線上面一層指派,相等是2,不等是1
}
for(int L = N - 3;L >= 0;L--){
for(int R = L + 2;R < N;R++){
dp[L][R] = Math.max(dp[L][R - 1],dp[L + 1][R]);//左和下左對比
if(str[L] == str[R]){//如果相等,繼續往左下角周遊
dp[L][R] = Math.max(dp[L][R],(2 + dp[L + 1][R - 1]));
}
}
}
return dp[0][N - 1];
}
}
3.3、三種方案的執行結果:
4、三種方案的基本思想如下:
4.1、從上到下,從左到右,每個格子裡的值就是需要傳回的值,是以取最大值傳回即可。
4.2、從嘗試該動态規劃,隻需要把位置找對就行。
到此,該算法分享完畢,大家一定要多多練習,勤于思考,早日成為大牛!