1
2
動態(tài)規(guī)劃的解法
以adbca為例子
狀態(tài)數(shù)組dp[i][j]表示從 i~j最大的回文串長度
狀態(tài)轉(zhuǎn)移方程為
初始狀態(tài)數(shù)組
a\d\b\c\a
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 1 | ||||
| 2 | 0 | 1 | |||
| 3 | 0 | 0 | 1 | ||
| 4 | 0 | 0 | 0 | 1 | |
| 5 | 0 | 0 | 0 | 0 | 1 |
第一次遍歷 len = 2時 狀態(tài)數(shù)組
ad\db\bc\ca
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 1 | 1 | |||
| 2 | 0 | 1 | 1 | ||
| 3 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 0 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 |
第三次遍歷 len = 3
adb\dbc\bca
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | ||
| 2 | 0 | 1 | 1 | 1 | |
| 3 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 |
第四次遍歷 len = 4
adbc\dbca
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | |
| 2 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 |
第五次遍歷 len = 5
adbca
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 3 |
| 2 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 |
代碼
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
char[] array = sc.next().toCharArray();
//字符串長度
int N = array.length;
int[][] dp = new int[N][N];
//狀態(tài)數(shù)組
for(int i = 0; i < N;dp[i][i] = 1,i++){}
for(int len = 2; len <= N;len++ ){
for(int i = 0; i + len <= N;i++){
if(array[i] == array[i+len-1]){
dp[i][i+len-1] = dp[i+1][i+len-2]+2;
}
dp[i][i+len-1] = Math.max(dp[i][i+len-1],Math.max(dp[i][i+len-2],dp[i+1][i+len-1]));
}
}
System.out.println(dp[0][N-1]);
思考
該問題具有最優(yōu)子結(jié)構(gòu)問題戈钢，從i - j 的最長回文串等于 i+1~j-1的最長回文串+2 或 i+1~j 或 i~j-1的最長回文串
只要知道了狀態(tài)轉(zhuǎn)移的規(guī)律邢笙，就可以很容易寫出代碼
