DP: Longest Palindromic Subsequence

會寫這題是因為碰到 Work Application 這家公司的徵才文 ( 新鮮人年薪150w up lol)

不過他的題目不是這樣,先附上我整理完的來源

第一個方法比較暴力 時間複雜度是 O(N²) 。

先來個概念解說

總之就是先看 目前 左右端 相不相等

不相等的話 刪除 左邊比較好 還是右邊比較好 的 一個算法

主程式

public static void main(String[] args) {
String s = "1545335451";
Palindrome.s = s;
int N = s.length();
dp = new int [N][N];
p = new int [N][N];
System.out.println("最長迴文子序列的長度是"+f(0, N-1));
System.out.println("最長迴文子序列是");
print(0, N-1);
}

p 是用來列印的時候用的。

public static int f(int i, int j){
if (i == j) return 1;
if (i > j) return 0;
if (dp[i][j] != 0) return dp[i][j]; //已經知道這個的結果了
// 左右兩端字元相等,定能形成更長迴文,同時從兩端縮小問題範疇。
if (s.charAt(i) == s.charAt(j)){
dp[i][j] = f(i+1, j-1) + 2;
p[i][j] = 0;
}
// 刪除左端字元比較好。
else if (f(i+1, j) > f(i, j-1)){
dp[i][j] = f(i+1, j);
p[i][j] = 1;
}
// 刪除右端字元比較好。
else if (f(i+1, j) < f(i, j-1)){
dp[i][j] = f(i, j-1);
p[i][j] = 2;
}
// 可以刪除其中一端的字元,都一樣好。
else /* if (f(i+1, j) == f(i, j-1)) */{
dp[i][j] = f(i, j-1);
p[i][j] = 3;
}
return dp[i][j];
}

print

static void print(int i, int j) {
if (i > j)return;
// 當迴文長度為奇數,最中間的字母。
if (i == j)
System.out.print(s.charAt(i));
// 兩端字母一樣。
else if (p[i][j] == 0) {
System.out.print(s.charAt(i));
print(i + 1, j - 1);
System.out.print(s.charAt(i));
}
// 刪除左端字元。
else if (p[i][j] == 1)
print(i + 1, j);
// 刪除右端字元。
else
print(i, j - 1);
}

第二個方法 ( Manacher’s Algorithm)

運用了 Gusfield’s Algorithm 的概念。時間複雜度為 O(N) 原理是建立在Z function 或稱Z value上。http://momo-funnycodes.blogspot.tw/2012/07/gusfield-algorithm.html

首先 Z function 真的有點難懂 ( 對我這個菜鳥來說 ),我想自己去看一下大概就知道了。最後字串比對如何應用,其實那篇(Gusfield’s Algorithm 的概念)裡面有說。

然後第二個方法其實我看不懂= =


最後其實我本來想要解的問題是

(work application) 類似問似問說一個字串的每個字,以那個字為中心可以造出幾個回文 subsequence

其實我自己想不出到底要如何是好,最後請教別人(宇航 )

//#include<stdio.h>
//#include<stdlib.h>
#include <bits/stdc++.h>
//#define Min(a,b,c) min((a),min((b),(c)))
#define mp(a, b) make_pair((a), (b))
#define pii pair<int, int>
#define pll pair<LL, LL>
#define pb(x) push_back(x)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define EPS 1e-11
#define MEM(x) memset(x, 0, sizeof(x))
#define N 200005
#define M
#define pi 3.14159265359
using namespace std;
typedef long long LL;
int dp[1005][1005];
char c[100005];
LL DP(int l, int r)
{
if (l > r)
return 0;
if (dp[l][r])return dp[l][r];
if (l == r)return dp[l][r] = 1;
if (c[l] == c[r])return dp[l][r] = DP(l, r - 1) + DP(l + 1, r);
///這邊其實本來也有減 DP(l + 1, r - 1); 但是 又加回來了 (因為算外面兩個也是一種)
return dp[l][r] = DP(l, r - 1) + DP(l + 1, r) - DP(l + 1, r - 1); ////為啥要減DP(l + 1, r - 1); 是因為會重疊算到一部分
}
int main()
{
MEM(dp);
scanf("%s", c + 1);
// cout << c + 1;
printf("%danswer", DP(1, strlen(c + 1)));
system("pause");
}

結論 演算法好難= =

Show your support

Clapping shows how much you appreciated Bear熊’s story.