程式碼備份區

題意：

問題是，給一個字串，問最少要做多少 1.插入 2.刪除 3.替換 動作才行把這個字串變成回文

解法：

用dp[i][j] 表示 位置i到j最少需要用多少指令才行變成回文

所以是

dp[i][j] = dp[i+1][j-1] , str[i]==str[j]

dp[i][j] = MIN (dp[i+1][j-1],dp[i+1][j],dp[i][j-1])+1 , str[i]!=str[j]

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MIN(x,y)((x)<(y)?(x):(y))

char str[1001];
int dp[1001][1001];
int findDp(int i,int j){
    if(dp[i][j]==-1){
        if(i>=j)dp[i][j]=0;
        else{
            if(str[i]==str[j]){
                dp[i][j] = findDp(i+1,j-1);
            }else {
                dp[i][j] = MIN(findDp(i+1,j-1),MIN(findDp(i+1,j),findDp(i,j-1)))+1;
            }
        }
    }
    return dp[i][j];
}
int main(){
    int t,Case=0;
    scanf("%d",&t);
    gets(str);
    while(t--){
        gets(str);
        memset(dp,-1,sizeof(dp));
        printf("Case %d: %d\n",++Case,findDp(0,strlen(str)-1));
    }

    return 0;
}