lightoj 1033 区间dp

题目链接：http://lightoj.com/volume_showproblem.php?problem=1033

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int maxe = 50000;
const int maxn = 105;
const int INF  = 0x3f3f3f;

int dp[maxn][maxn];   //dp[i][j]表示字符串中从i到j最少要添加的字母个数。

int main()
{
    //freopen("E:\acm\input.txt","r",stdin);
    int T;
    cin>>T;
    for(int cas=1;cas<=T;cas++){
        char a[maxn];
        scanf("%s",a+1);
        int N = strlen(a+1);

        //memset(dp,0x3f,sizeof(dp));
        for(int i=1;i<=N;i++)  dp[i][i] = dp[i][i-1] = 0;

        for(int i=N;i>=1;i--)
            for(int j=i+1;j<=N;j++){
            if(a[i] == a[j]){
                dp[i][j] = dp[i+1][j-1];
            }
            else{
                dp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1;
            }
        }
        printf("Case %d: %d
",cas,dp[1][N]);
    }
}