LC2547 WA1

class Solution {
    using ll = long long;
    vector<vector<ll>> dp;
    ll search(vector<int>& ns, int k, int beg, int end) {
        if (dp[beg][end] != LLONG_MAX / 2) return dp[beg][end];
        if (beg + 1 == end) {
            return dp[beg][end] = k;
        }
        /*
        // map<int, int> cnt;
        vector<int> cnt(1 << 10);
        for (int i = beg; i < end; ++i) cnt[ns[i]]++;
        ll dup = 0;
        for (auto p: cnt) if (p >= 2) dup += p;

        dp[beg][end] = min(dp[beg][end], dup + k);
        */

        for (int i = beg + 1; i < end; ++i) {
            ll opt = search(ns, k, beg, i) + search(ns, k, i, end);
            printf("beg:%d i:%d end:%d opt:%lld\n", beg, i, end, opt);
            dp[beg][end] = min(dp[beg][end], opt);
        }
        return dp[beg][end];
    }
public:
    int minCost(vector<int>& nums, int k) {
        int n = nums.size();
        dp = vector<vector<ll>>(n + 1, vector<ll>(n + 1, LLONG_MAX / 2));
        for (int i = 0; i < n; ++i) {
            vector<int> cnt(1 << 10);
            ll val = k;
            for (int j = i; j < n; ++j) {
                cnt[nums[j]]++;
                if (cnt[nums[j]] == 2) val += 2;
                else if (cnt[nums[j]] > 2) val += 1;
                dp[i][j + 1] = val;
                cout << dp[i][j + 1] << ' ';
            }
            cout << endl;
        }
        return (int)search(nums, k, 0, nums.size());
    }
};