【DP入门】回文字符串

题目来自nyist第37题，如下：

描述

每行输出所需添加的最少字符数

DP解法，先找递推式，要求ai，ai+1，ai+2....aj序列的解，有两种情况，第一是ai == aj，则转换为求ai+1，ai+2 ... aj-1序列的解；第二是ai != aj，此时可能的最小解是在左边添上一个aj-1，这样便转换为第一种情况，或者在右边添上一个ai+1，也转换为第一种情况，而最终父问题的解就取自直接子问题以及第二种情况中两个子问题中的最小解。

由此只要求父问题需要先求子问题，自下而上递推；由于要求的子问题是1、2；2、3；3、4....n-1、n以及1、2、3；2、3、4；......n-2、n-1、n（数字代表字符串的下标）等等，即需要一个n*（n-1）/2大小的数组来存放自下而上的计算结果。本题中采用二维数组，其中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++)   //表示当前考虑的序列长度-1			for(i = 0;i < len-gap;i++)  //表示当前考虑的序列的起始字符下标			{				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]);	}}动规的题目代码量不算很大，但是个人感觉还是较为难想，还需要积累联系。