51nod 1720 祖玛

51nod 1720 祖玛

这又是一个区间 dp，但这题又和其他的不一样，这题又用记忆化搜索，但是多学一种方法也没事，但其实用搜索后就模拟即可了。

#include<bits/stdc++.h>
using namespace std;

// 定义全局变量
int n; // 数组长度
int dp[505][505]; // dp[l][r] 表示在区间 [l, r] 之间的最优解
int a[1005]; // 存储输入的数组

// dfs 函数使用动态规划和递归来计算区间 [l, r] 的最小值
int dfs(int l, int r) {
    // 基本情况：如果左边界超过右边界，返回 1
    if (l > r) {
        return 1;
    }

    // 如果 dp[l][r] 已经被计算过，直接返回结果
    if (dp[l][r]) {
        return dp[l][r];
    }

    // 初始化 dp[l][r] 为一个很大的值，表示我们要找到最小值
    dp[l][r] = INT_MAX;

    // 枚举区间的分割点 i，将区间分为 [l, i] 和 [i+1, r] 两个部分
    for (int i = l; i < r; i++) {
        // 递归计算两部分的值，并更新最小值
        dp[l][r] = min(dp[l][r], dfs(l, i) + dfs(i + 1, r));
    }

    // 如果数组的左右边界元素相等，可以尝试通过减少一层区间来优化结果
    if (a[l] == a[r]) {
        dp[l][r] = min(dp[l][r], dfs(l + 1, r - 1)); 
    }

    // 返回在区间 [l, r] 的最优解
    return dp[l][r];
}

int main() {
    ios::sync_with_stdio(false); // 关闭同步以提高输入输出效率

    // 输入数组的长度
    cin >> n;
    
    // 输入数组元素，从下标 1 到 n
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 调用 dfs 函数求解区间 [1, n] 的最优值，并输出结果
    cout << dfs(1, n);

    return 0;
}