给出n个数字，我们来逐步删除，如果一个子串是回文数，就可以直接删除，问删除完最少的次数。
设dp[i][j]为删除区间[i,j]所需最小次数
题解：记忆化搜索

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
const int inf = 1e9;
int dp[maxn][maxn], a[maxn];
int dfs(int i, int j) {
    if (i >= j) return 1;
    if (dp[i][j]) return dp[i][j];
    int ans = inf;
    if (a[i] == a[j]) ans = min(ans, dfs(i + 1, j - 1));
    for (int k = i; k < j; k++) ans = min(ans, dfs(i, k) + dfs(k + 1, j));
    return dp[i][j] = ans;
}
int main() {
    int n; 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << dfs(1, n) << endl;
    return 0;
}

题解：dp

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int dp[maxn][maxn], a[maxn];
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= j; i++) {
            dp[i][j] = dp[i][j - 1] + 1;
            for (int k = i; k < j; k++) {
                if (a[j] == a[k]) {
                    dp[i][j] = min(dp[i][j], dp[i][k - 1] + max(dp[k + 1][j - 1], 1));
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}