[알고리즘] 최소 문자 수 구성 을 추가 하여 문자열 을 회 문 으로 구성 합 니 다.

 http://poj.org/problem?id=1159
Description
A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome. 
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome. 
Input
Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.
Output
Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.
Sample Input

5

Ab3bd

Sample Output

2

Source
IOI 2000
 
나 는 이 문 제 를 보고 첫 번 째 시간 에 재 귀 알고리즘 으로 직접 만 들 었 다. 몇 줄 의 코드 만 있 으 면 매우 간단 하 다. 그러나 제출, 어, 시간 초과 야. 재 귀 에 중복 작업 이 많은 것 같 아서 동적 계획 알고리즘 으로 이 문 제 를 해결 하고 싶 었 다.
알고리즘 은 다음 과 같 습 니 다.
문자열
str，
왼쪽 은 현재 문자열 의 가장 왼쪽 문자 의 색인 아래 에 표 시 됩 니 다.
right 는 현재 문자열 의 가장 오른쪽 문자 의 색인 아래 표 시 됩 니 다.
1. 문자열 이 한 글자 만 있 으 면 0 을 되 돌려 줍 니 다.
2. 문자열 에 두 글자 가 있 으 면 0 을 되 돌려 줍 니 다. 그렇지 않 으 면 1 을 되 돌려 줍 니 다.
3. 문자열 3 개 또는 3 개 이상 은 다음 과 같은 상태 전이 방정식 이 있다.
    1)、str[left] == str[right];minAdd (str, left, right) = minAdd (str, left + 1, right - 1)
    2)、str[left] != str[right]；minAdd (str, left, right) = 1 + min (minAdd (str, left, right - 1), minAdd (str, left + 1, right);
 
 
m [] [] 로 left ~ right 문자열 을 기록 하여 답장 에 필요 한 최소 문자 수 를 구성 하면 중복 계산 을 피 할 수 있 습 니 다.
구체 적 으로 코드 에서 m [] [] 의 초기 화 와 구 조 를 볼 수 있다.

#include <iostream>

using namespace std;

const short N = 5001;

short m[N][N];

short  foo(char* str,short left,short right)

{

    if(left  == right)

    {

        return m[left][right] = 0;

    }

    else if( left + 1 == right )

    {

        if( str[left] == str[right] )

        {

            return m[left][right] = 0;

        }

        else

        {

            return m[left][right] = 1;

        }

    }

    else

    {

        if( m[left][right] != -1 )

        {

            return m[left][right]; 

        }

        else

        {

            if(str[left] == str[right])

            {

                return m[left][right] = foo(str,left + 1, right - 1);

            } 

            else

            {

                short a = foo(str,left, right - 1) + 1;

                short b = foo(str,left + 1, right) + 1;

                return m[left][right] = a < b ? a : b;    

            }

        } 

    }

}

int main(int argc, char** argv) { 

    char str[N];

    short i, j, n;

    for( i = 0; i < N; ++i)

    {

        for(j =0; j < N; ++j)

        {

            m[i][j] = -1;

        }

    }

    cin>>n;

    i = 0; 

    while(i < n)

    {

        cin>>str[i++];

    }

    str[i]=0;

    cout<<foo(str,0,n - 1); 

    return 0;

}

원래 2 차원 배열 m [N] [N] 은 int 형 이지 만 OJ 보고 메모리 가 제한 을 초과 하여 short 를 사용 하면 5000 을 덮어 쓸 수 있 습 니 다. 제목 요구 가 2 < N < 5001 이거 나 스크롤 배열 을 사용 할 수 있 기 때문에 다음 과 같은 다른 코드 를 볼 수 있 습 니 다.

#include <iostream>

#include <cstring>

using namespace std;

const int N = 5001;

short m[2][N];

short foo(char* str, short n)

{

    short i, j, k, k1, k2, a, b;

    for(k = 1; k < n; ++k)

    {

        k1 = k & 1;

        k2 = (k - 1) & 1;

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

        {

            j = i + k;

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

            {

                m[k1][i] = m[k1][i+1];

            }

            else

            {

                m[k1][i] = 1 + (m[k2][i] < m[k2][i+1] ? m[k2][i] : m[k2][i+1]); 

            }

        }

    }

    return m[(n-1)&1][0];

}

int main(int argc, char** argv) { 

    char str[N];

    short i, n;

    i = 0; 

    cin>>n;

    while(i < n)

    {

        cin>>str[i++];

    }

    str[i]=0;

    cout<<foo(str,n);

    return 0;

}

여기 서 하나의 스크롤 배열 을 사용 하여 & 1 을 묘 용 했 습 니 다. 바로 2 개의 1 차원 배열 을 번갈아 사용 하여 수량 급 의 공간 복잡 도 를 낮 추 는 것 입 니 다.
 
코드 를 한 번 쓰 면 소감 이 있 는 것 같 습 니 다. 알고리즘 은 실현 을 통 해 공 고 히 파악 해 야 할 것 같 습 니 다.
 
본 고 는 지식 공유 서명 - 비상 업적 사용 3.0 허가 협의 을 바탕 으로 허 가 를 진행한다.전재, 연역 을 환영 하지만 본 고의 서명 숲 의 날개 가 날리다. 을 보류 해 야 합 니 다. 문의 가 필요 하 시 면 편 지 를 보 내 주세요.