Xóa hộp (Remove Boxes) trong C++

Cho dãy hộp màu (số nguyên dương). Mỗi lượt chọn đoạn liên tiếp cùng màu độ dài k, xóa được k² điểm. Tối đa hóa tổng điểm.

Ví dụ

[1,3,2,2,2,4,4,3,1] → 21.

DP 3 chiều dp[i][j][k]

dp[i][j][k] = điểm max cho đoạn [i..j] với k hộp cùng màu boxes[i] liền trước i. Chuyển trạng thái: gom hộp cùng màu liền kề, hoặc tách tại vị trí cùng màu xa hơn.

Chương trình C++

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

class Solution {
    int solve(vector<int>& boxes, int i, int j, int k, 
              vector<vector<vector<int>>>& dp) {
        if(i>j) return 0;
        if(dp[i][j][k]!=-1) return dp[i][j][k];
        // Gom các hộp cùng màu liên tiếp
        for(; i+1<=j && boxes[i+1]==boxes[i]; i++, k++);
        int ret = (k+1)*(k+1) + solve(boxes, i+1, j, 0, dp);
        // Thử tách tại hộp cùng màu xa hơn
        for(int x=i+1; x<=j; x++) {
            if(boxes[x]==boxes[i]) {
                ret = max(ret, solve(boxes, i+1, x-1, 0, dp) 
                             + solve(boxes, x, j, k+1, dp));
            }
        }
        return dp[i][j][k] = ret;
    }
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n+1, vector<int>(n+1, -1)));
        return solve(boxes, 0, n-1, 0, dp);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,3,2,2,2,4,4,3,1};
    cout << ob.removeBoxes(v); // 21
    return 0;
}