題目來自nyist第37題，如下：

描述

每行輸出所需添加的最少字符數(shù)

DP解法，先找遞推式，要求ai，ai+1，ai+2....aj序列的解，有兩種情況，第一是ai == aj，則轉(zhuǎn)換為求ai+1，ai+2 ... aj-1序列的解；第二是ai != aj，此時可能的最小解是在左邊添上一個aj-1，這樣便轉(zhuǎn)換為第一種情況，或者在右邊添上一個ai+1，也轉(zhuǎn)換為第一種情況，而最終父問題的解就取自直接子問題以及第二種情況中兩個子問題中的最小解。

由此只要求父問題需要先求子問題，自下而上遞推；由于要求的子問題是1、2；2、3；3、4....n-1、n以及1、2、3；2、3、4；......n-2、n-1、n（數(shù)字代表字符串的下標(biāo)）等等，即需要一個n*（n-1）/2大小的數(shù)組來存放自下而上的計算結(jié)果。本題中采用二維數(shù)組，其中dp[i][j]表示從第i個字符到第j個字符所組成的序列的解。

代碼如下：

#include <stdio.h>#include <string.h>#include <stdlib.h>int dp[1000][1000+2];int main(){	int N,i,j,gap,len;	char s[1000+5];	scanf("%d",&N);	while(N--)	{		memset(dp,0,sizeof(dp));		scanf("%s",s);		len = strlen(s);		for(i = 0;i < len;i++)	dp[i][i] = dp[i][i-1] = 0;		for(gap = 1;gap < len;gap++)   //表示當(dāng)前考慮的序列長度-1			for(i = 0;i < len-gap;i++)  //表示當(dāng)前考慮的序列的起始字符下標(biāo)			{				j = i + gap; //end 				dp[i][j] = 1000;//任意的大值即可				if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1];				dp[i][j] = dp[i][j] > (dp[i+1][j]+1) ? (dp[i+1][j]+1) : dp[i][j];				dp[i][j] = dp[i][j] > (dp[i][j-1]+1) ? (dp[i][j-1]+1) : dp[i][j];			}		PRintf("%d/n",dp[0][len-1]);	}}動規(guī)的題目代碼量不算很大，但是個人感覺還是較為難想，還需要積累聯(lián)系。