Chương trình đếm số phép xóa dãy con đối xứng để làm rỗng mảng trong C++

Mô tả bài toán

Cho mảng nums. Mỗi phép toán xóa một dãy con là palindrome. Tìm số phép tối thiểu để xóa hết mảng.

Ví dụ: nums = [6,2,4,4,2,10,6] → 2 (xóa [2,4,4,2] rồi [6,10,6]).

Giải thuật (Quy hoạch động + Đệ quy có nhớ)

1. dp[i][j] = số phép tối thiểu cho đoạn i..j.
2. Đệ quy dfs(i, j):
   • Nếu i > j: return 0.
   • Nếu i == j: return 1.
   • Nếu j-i == 1: return (v[i]==v[j] ? 1 : 2).
   • Nếu v[i]==v[i+1]: ret = 1 + dfs(i+2, j).
   • Nếu dp[i][j] đã tính: return dp[i][j].
   • ret = min(ret, 1 + min(dfs(i+1,j), dfs(i,j-1))).
   • Nếu v[i]==v[j]: ret = min(ret, dfs(i+1,j-1)).
   • Với k từ i+2 đến j-1: nếu v[i]==v[k] thì ret = min(ret, dfs(i+1,k-1)+dfs(k+1,j)).
   • Lưu dp[i][j] = ret.
3. Gọi dfs(0, n-1).

Ví dụ minh họa (C++)

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

int dp[105][105];

int dfs(int i, int j, vector<int>& v) {
    int ret = INT_MAX;
    if (i > j) return 0;
    if (i == j) return 1;
    if (j - i == 1) return v[i] == v[j] ? 1 : 2;
    if (i + 1 <= j && v[i] == v[i + 1]) {
        ret = 1 + dfs(i + 2, j, v);
    }
    if (dp[i][j] != -1) return dp[i][j];
    ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
    if (v[i] == v[j]) {
        ret = min(ret, dfs(i + 1, j - 1, v));
    }
    for (int k = i + 2; k < j; k++) {
        if (v[i] == v[k]) {
            ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
        }
    }
    return dp[i][j] = ret;
}

int solve(vector<int>& nums) {
    memset(dp, -1, sizeof dp);
    int n = nums.size();
    return dfs(0, n - 1, nums);
}

int main() {
    vector<int> v = {6, 2, 4, 4, 2, 10, 6};
    cout << solve(v);
    return 0;
}

Đầu vào

{6, 2, 4, 4, 2, 10, 6}

Đầu ra

2