D. Zuma

dp, palindrome

출처: Codeforces D. Zuma

SOL)
dp[l][r]의 최소값은 dp[l][r] = min(dp[l][r], dp[l][k-1] + dp[k+1][r-1])이다.
k는 r -1보다 작은데 이유는 생각해보면
1 1 2 3 2 경우 k = 3, r = 5라고 해보자
arr[k] == arr[r]이므로 문자열 2 3 2는 한번에 없어진다. 따라서 위식이 성립한다.
그런데 만약 k가 r까지 커진다고 하면 달라진다.
1 1 2 3 3 경우 k = 4, r = 5라고 해보자.
dp[l][k-1]은 올바른 값을 가지지만 dp[k+1][r-1]은 0을 가리키고 잇을것이다.
하지만 3 3을 없애는데에도 비용 1이 들기 때문에 이는 아래에서
예외처리 해준다.

*dp[l][r] = dp[l][r-1] + 1로 초기화 해주는데
dp[l][r] = dp[l+1][r]로 초기화는 안된다.
가장 최소값을 갖지 못하는 경우가 발생하는데
예외는
3
1 1 2 이다.

[-] Collapse

#include<iostream>
#include<algorithm>
using namespace std;

int arr[510];
int n;
int dp[510][510];

int main(){
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);

    for (int r = 1; r <= n; r++){
        dp[r][r] = 1;
        for (int l = r-1; l >= 1; l--){
            dp[l][r] = dp[l][r-1] + 1;
            for (int k = l; k < r - 1; k++){
                if (arr[k] == arr[r])
                    dp[l][r] = min(dp[l][r], dp[l][k - 1] + dp[k + 1][r - 1]);
            }
            if (arr[r - 1] == arr[r])
                dp[l][r] = min(dp[l][r], 1 + dp[l][r - 2]);
        }
    }
    printf("%d", dp[1][n]);
}