题目描述

给你一个整数数组 arr，每一次操作你都可以选择并删除它的一个 回文 子数组 arr[i], arr[i+1], ..., arr[j]，其中 i <= j。

注意，每当你删除掉一个子数组，右侧元素都会自行向前移动填补空位。

请你计算并返回从数组中删除所有数字所需的最少操作次数。

样例

输入：arr = [1,2]
输出：2

输入：arr = [1,3,4,1,5]
输出：3
解释：先删除 [4]，然后删除 [1,3,1]，最后再删除 [5]。

限制

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 20

算法

(动态规划，区间模型) $O(n^3)$

1. 设 $f(i, j)$ 表示删除区间 $[i, j]$ 所需要的最少操作次数。
2. 初始时，$f(i, i) = 1$，$f(i, i - 1) = 0$。其余为正无穷。
3. 转移时，可以将 $arr[i]$ 单独考虑删除，则转移 $f(i, j) = min(f(i, j), 1 + f(i + 1, j))$。如果 $arr[i] == arr[i + 1]$，则这两个可以一起删除，转移 $f(i, j) = min(f(i, j), 1 + f(i + 2, j))$。如果 $arr[i] == arr[k], (i + 2 <= k <= j)$，则 $arr[i]$ 和 $arr[k]$ 可以随着区间 $[i + 1, k - 1]$ 一起删除，转移 $f(i, j) = min(f(i, j), f(i + 1, k - 1) + f(k + 1, j))$。
4. 最终答案为 $f(0, n - 1)$。

时间复杂度

• 状态数为 $O(n^2)$ 个，转移需要 $O(n)$ 的时间，故时间复杂度为 $O(n^3)$。

空间复杂度

• 需要额外 $O(n^2)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    int minimumMoves(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> f(n + 1, vector<int>(n + 1));

        for (int i = 0; i <= n; i++)
            f[i][i] = 1;

        for (int i = 1; i <= n; i++)
            f[i][i - 1] = 0;

        for (int len = 2; len <= n; len++)
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                f[i][j] = 1 + f[i + 1][j];
                if (arr[i] == arr[i + 1])
                    f[i][j] = min(f[i][j], 1 + f[i + 2][j]);

                for (int k = i + 2; k <= j; k++)
                    if (arr[i] == arr[k])
                        f[i][j] = min(f[i][j], f[i + 1][k - 1] + f[k + 1][j]);
            }

        return f[0][n - 1];
    }
};