NYOJ 37 -回文字符串

NYOJ 37 ---回文字符串

点击打开链接NYOJ37

题目：                                                                    回文字符串

#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <stack>#include <queue>#include <cmath>#include <set>using namespace std;#define MAXN 1010int n;char ch[MAXN];int dp[MAXN][MAXN];int min(int a , int b){ return a<b?a:b;}void solve() { memset(dp , 0 , sizeof(dp)); int len = strlen(ch); int i , j , k , l; for(l = 1 ; l < len ; l++){ for(i = 0 ; i <= len-l ; i++){ j = i+l ; if(ch[i] == ch[j]) dp[i][j] = dp[i+1][j-1]; else dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1; } } printf("%d\n" , dp[0][len-1]);}int main() { //freopen("input.txt" , "r" , stdin); scanf("%d%*c" , &n); while(n--){ gets(ch) ; solve(); } return 0;}