USACO金牌题目 Space Jazz (range DP)

#include <bits/stdc++.h>

using namespace std;

const int N=501;

int dp[N][N];

int main()

{

    string s;

    cin>>s;

    int n=s.size();

    for(int j=0;j<n;j++){

        for(int i=j;i>=0;i--){

            int res=1+dp[i+1][j];

            for(int k=i+1;k<=j;k++){

                if(s[i]==s[k]){

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

                }

            }

            dp[i][j]=res;

        }

    }

    cout<<dp[0][n-1];

    return 0;

}