hdu 2476 구간 dp

두 과정과 관련되므로, 먼저 하나의 빈 열을 b열로 바꾸는 최소 비용을 계산해야 한다.
dp[i][j] = min ( dp[i][j-1] + 1 , dp[i][k] + dp[k+1][j](b[j]==b[k] );
첫 번째 상황은 앞에 칠한 상태에서 j 브러시 문자를 직접 칠하는 거예요.
두 번째 상황은 j와 k의 문자가 같을 때 우리는 k에서 j를 한 번 닦을 수 있다. 그러면 소비는 k 이전의 한 번 닦는 대가와 k+1에서 j-1 사이의 한 번 닦는 대가의 합이다. 왜냐하면 j와 k는 동시에 닦이기 때문에 k는 앞의 구간에서 닦는 동시에 j를 닦고 그 다음에 닦는 부분의 합이다.
다음은 a열을 b열로 전환하는 과정입니다. 전환하는 과정은 현재 위치의 문자와 b열이 같으면 최소 비용이 변하지 않고 같지 않으면 앞의 어느 분부터 이런 색을 칠한 다음에 빈 열로 처리하면 됩니다. 매번 현재가 마지막 자리이기 때문에 마지막 자리까지 스캔할 때 무겁지 않고 빠뜨리지 않습니다.
코드는 다음과 같습니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 107

using namespace std;

int dp[MAX][MAX];

char a[MAX];
char b[MAX];
int ans[MAX];

int main ()
{
	while ( ~scanf ( "%s" , a+1 ) )
    {
	    scanf ( "%s" , b+1 );
	    int n = strlen ( a+1 );
        memset ( dp , 0 , sizeof ( dp ) );
	    for ( int i = 1; i <= n ; i++ )
		    dp[i][i] = 1;
	    for ( int i = 1 ; i < n ; i++ )
            for ( int j = 1 ; j <= n-i ; j++ )
            {
                dp[j][j+i] = dp[j][j+i-1] + 1;
			    for ( int k = j ; k < j+i ; k++ )
				    if ( b[j+i] == b[k] )
					    dp[j][j+i] = min ( dp[j][j+i] , dp[j][k] + dp[k+1][j+i-1] );
				    /*if ( a[k] == b[k] )
				    {
					    int temp = 0;
					    if ( k-1>=j ) 	temp += dp[j][k-1];
					    if ( k+1<=i+j ) temp += dp[k+1][i+j];
                        // if (j == 0 && i+j == n-1 ) cout << "No : " << temp << endl;
					    dp[j][j+i] = min ( dp[j][j+i] , temp );
				    }*/
			 }
       for ( int i = 1 ; i <= n ; i++ )
           ans[i] = dp[1][i];
       for ( int i = 1 ; i <= n ; i++ )
       {
            if ( a[i] == b[i] )
                ans[i] = ans[i-1];
            else
                for ( int j = 1 ; j < i ; j++ )
                   ans[i] = min ( ans[i] , ans[j] + dp[j+1][i] );
       }
	   printf ( "%d
" , ans[n] );
    }
}