UVa 10739 String to Palindrome(클래식 메신저 구간 DP)

제목:
문자열을 지정하면 삭제, 삽입, 교체 작업을 할 수 있습니다.
최소 몇 번의 조작을 거치면 이 문자열을 회문 문자열로 바꿀 수 있습니다.
아이디어:
삽입/삭제 작업만 수행할 수 있었던 이전 메모 문자열과 유사하게 이번에는 교체 작업이 하나 더 생겨서 다음과 같은 몇 가지 상황이 생겼다.
(구간 DP는 끊임없이 양면으로 확대됨)
1.s[i]=s[j]는 분명히 i와 j 사이의 문자열만 고려하면 된다. 이때 dp[i][j]=dp[i+1][j-1].
2. s[i] != s[j] 이때 삭제, 삽입 또는 교체를 고려해야 한다.삭제와 삽입에 필요한 작업 단계와 영향이 일치하기 때문에
삽입이나 삭제만 고려하면 됩니다.삽입에 대해서는 dp[i][j]=min(dp[i+1][j], dp[i][j-1])+1;교체에 대해서는 dp[i][j]=min(dp[i][j], dp[i+1][j-1]+1)이 있다.

#include <cstdio>

#include <cstdlib>

#include <cstring>



#define min(a,b) (((a) < (b)) ? (a) : (b))



const int MAXN = 1010;

char str[MAXN];

int dp[MAXN][MAXN];



int main()

{

    int cases, cc = 0;

    scanf("%d", &cases);

    while (cases--)

    {

        scanf("%s", str);

        int n = strlen(str);

        for (int i = 0; i < n; ++i)

        {

            dp[i][i] = 0;

            if (str[i] == str[i+1])

                dp[i][i+1] = 0;

            else

                dp[i][i+1] = 1;

        }



        for (int p = 2; p < n; ++p)

        {

            for (int i = 0, j = p; j < n; ++i, ++j)

            {

                if (str[i] == str[j])

                    dp[i][j] = dp[i+1][j-1];

                else

                {

                    dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;

                    dp[i][j] = min(dp[i][j], dp[i+1][j-1] + 1);

                }

            }

        }

        printf("Case %d: %d
", ++cc, dp[0][n-1]);

    }

    return 0;

}