回文字符串。动态规划。

题目

描述

给定一个字符串 S ，最少需要几次增删改操作可以把 S 变成一个回文字符串？一次操作可以在任意位置插入一个字符，或者删除任意一个字符，或者把任意一个字符修改成任意其他字符。

输入

字符串 S。S 的长度不超过100, 只包含’A’-‘Z’。

输出

最少的修改次数。

样例输入

ABAD

样例输出

分析

这题采用动态规划。

读入的字符串假设用s表示。则s[i..j]，表示从下标为i的字符到下标为j的字符所组成的字符子串（字符串下标从0开始），而s[i]表示下标为i的字符。例如，字符串“ABCD”，则s[0,2]表示字符串“ABC”，s[1]为字符“B”。

用一个二维数组dp[i][j]来保存状态，其中对于每个dp[i][j]，表示对字符串s[i..j]，使之成为回文字符串所需的最少操作。

现在考察子串s[i..j]。

第一种情况，首尾恰好相同，即 s[i] == s[j]。则对于子串s[i..j]而言，它要变成回文字符串所需的最少操作，与子串s[i-1..j-1]变成回文字符串所需的最少操作数相同。所以有 dp[i][j] = dp[i-1][j+1]

第二种情况，首尾不同，即 s[i] != s[j]。要想让子串s[i..j]变成回文字符串，我们可以利用题目提供的三种操作：增加，删除，修改。

接下来我们分情况讨论。

假设 s[i..j-1] 是回文字符串。则我们可以在s[i]之前添加上一个字符，使之匹配字符s[j]，从而让 s[i..j] 成为回文字符串。此时，dp[i][j] = dp[i][j-1] + 1。或者，我们直接删除掉字符s[j]，让 s[i..j] 变成s[i..j-1]，从而成为回文字符串，此时同样，dp[i][j] = dp[i][j-1] + 1
假设 s[i+1..j] 是回文字符串。则我们可以在s[j]之后添加一个字符，使之匹配字符s[i]，从而让 s[i..j] 成为回文字符串，此时，dp[i][j] = dp[i+1][j] + 1。或者，我们直接将字符s[i]删掉，让 s[i..j] 变成 s[i+1，j]，从而成为回文字符串，此时也有 dp[i][j] = dp[i+1][j] + 1。
假设 s[i-1..j-1] 是回文字符串。则我们可以修改s[i]，使之匹配s[j]，或者修改s[j]，使之匹配s[i]。这种情况下，有：d[i][j] = dp[i-1][j-1] + 1

以上三种情况，囊括了对字符串s[i..j]所能操作的所有情况。而为求最小操作数，只要取三种情况的最小值。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define MAX_N 1005
using namespace std;
char str[MAX_N];
int dp[MAX_N][MAX_N];
int min_dp(int a,int b,int c){
    int temp = a>b?b:a;
    return temp>c?c:temp;
}
int main()
{
    scanf("%s",str);
    int len = strlen(str);
    memset(dp, 0, sizeof(dp));
    for (int i=len-1 ;i>=0 ;i--){
        for (int j=i ;j<len ;j++){
            if ( str[i] == str[j]){
                dp[i][j] = dp[i+1][j-1];
            }else{
                dp[i][j] = min_dp(dp[i+1][j],dp[i][j-1],dp[i+1][j-1]) + 1;
                }
            }
        }
    }
    printf("%d",dp[0][len-1]);
    return 0;
}