Codeforces 607B Zuma（区间DP）

题目链接 Zuma

区间DP……好奇妙啊……参考了别人的代码……现在都有点糊涂……

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)    for (int i(a); i <= (b); ++i)

const int N   = 510;

int a[N];
int f[N][N];
int n;

int dp(int l, int r){
        if (~f[l][r]) return f[l][r];
        if (l == r) return 1;
          if (l > r) return 0;
        int ret = 1 + dp(l + 1, r);
        rep(i, l + 2, r) if (a[l] == a[i]) ret = min(ret, dp(l + 1, i - 1) + dp(i + 1, r));
        if (a[l] == a[l + 1]) ret = min(ret, 1 + dp(l + 2, r));
        return f[l][r] = ret;
}
                
int main(){

    scanf("%d", &n);
        rep(i, 1, n) scanf("%d", a + i);
        memset(f, -1, sizeof f);
        printf("%d
", dp(1, n));
    return 0;

}