poj 1159 palindrome

/*
busyfisher 2013/6/20

動态規劃

dp[i][j] 表示以str[i]開始以str[j]結束的子字元串稱為回文需要加入的最少字元數

遞推式如下：

Memory: 40756K		Time: 1485MS
Language: C++		Result: Accepted

*/
           

#include <iostream>
#include <string>

using namespace std;

#define maxn 5000+10

int n;
string str;

short dp[maxn][maxn];

int _dp(){
	for(int i = 0; i< n;i++)
		dp[i][i] = 0;

	for(int i = 0; i< n-1;i++){
		if (str[i] == str[i+1])
			dp[i][i+1] = 0;
		else
			dp[i][i+1] = 1;
	}

	for(int len = 2; len < n ; len++)
		for(int i = 0,j = len; j < n; i++,j++){
			if(str[i] == str[j])
				dp[i][j] = dp[i+1][j-1];
			else
				dp[i][j] = min(dp[i][j-1],dp[i+1][j])+1;
	}
	return dp[0][n-1];
}

int main(){
	cin>>n;
	cin>>str;
	cout<<_dp()<<endl;
	return 0;
}