UVA 10739 String to Palindrome 转换回文 dp递推 - c++编程基础

题意：给出一个字符串，可以添加删除字符，或替换字符，求把它变成回文的最少操作次数。

可以用递推或者递归，其实递归更好理解，递推还要确定滚动方向。

dp[i][j]表示字符i到j位置上最少需要几步构成回文。

dp方法为：如果str[i] = str[j]，dp[i][j]=dp[i + 1][j - 1]; 否则dp[i][j] = min(dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1]) + 1

由于定义min是没括上括号，调了老旧 - -

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        uva10739.cpp 
*  Create Date: 2013-11-08 15:20:51 
*  Descripton:  dp  
*/  
  
#include   
#include   
  
#define min(a, b) ((a) < (b)   (a) : (b))  
  
const int MAXN = 1010;  
  
int dp[MAXN][MAXN];  
char ch[MAXN];  
int t, cas;  
  
int main() {  
    scanf("%d", &t);  
    for (cas = 1; cas <= t; cas++) {  
        scanf("%s", ch);  
        int len = strlen(ch);  
  
        for (int i = 0; i < len; i++)  
            dp[i][i] = 0;  
  
        for (int i = len - 1; i >




= 0; i--)  
            for (int j = i + 1; j < len; j++)  
                if (ch[i] == ch[j])  
                    dp[i][j] = dp[i + 1][j - 1];  
                else  
                    dp[i][j] = min(min(dp[i + 1][j], dp[i + 1][j - 1]), dp[i][j - 1]) + 1;  
  
        printf("Case %d: %d\n", cas, dp[0][len - 1]);  
    }  
    return 0;  
}