HDU - 2476 String painter

제목: 두 개의 길이를 똑같이 정하고 소문자로 구성된 문자열 s와 t만 한 걸음 한 걸음 s의 연속적인 서브열을 같은 자모로 만들 수 있다. 적어도 몇 걸음이 걸려야 s를 t로 만들 수 있느냐고 묻는다.
사고방식: 먼저 예처리를 하고 s열과 t열이 같은 알파벳이 없다고 가정하면 dp[i][j]로 i에서 j까지 t와 같은 최소 걸음수를 나타낸다. 그러면 dp[i][j]=dp[i+1][j]를 초기화하면 유일하게 걸음수를 낮출 수 있는 것은 t[i]=t[k](i+1<=k<=j)가 존재할 수 있다. 그러면 분명히 i, j에서 t[i]로 먼저 걸음수를 계산할 수 있기 때문에 t[i]는 계산하지 않고 [dpi+1][dpk]+j]를 고려하면 [dpk+j]가 예처리를 끝난다.ans[i]를 설정하면 전 i자리의 최소값을 표시하고, 이전 위치를 일일이 열거하여 최소값을 구한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 105;

char s1[MAXN],s2[MAXN];
int dp[MAXN][MAXN];
int ans[MAXN];

int main(){
    while (scanf("%s%s",s1,s2) != EOF){
        int len = strlen(s1);
        memset(dp,0,sizeof(dp));
        for (int j = 0; j < len; j++){
            for (int i = j; i >= 0; i--){
                dp[i][j] = dp[i+1][j]+1;
                for (int k = i+1; k <= j; k++)
                    if (s2[i] == s2[k])
                        dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
            }
        }
        cout << dp[0][len-1] << endl;
        for (int i = 0; i < len; i++)
            ans[i] = dp[0][i];
        for (int i = 0; i < len; i++){
            if (s1[i] == s2[i])
                ans[i] = ans[i-1];
            else {
                for (int j = 0; j < i; j++)
                    ans[i] = min(ans[i],ans[j]+dp[j+1][i]);
           }
        }
        printf("%d
",ans[len-1]);
    }
    return 0;
}