ลบกล่อง (Remove Boxes) ใน C++

ภาพรวมปัญหา

มีกล่องสีต่างๆ (แทนด้วยตัวเลข) ลบกล่องได้หลายรอบ แต่ละรอบเลือกกล่องติดกันสีเดียวกัน k กล่อง ลบได้ k² คะแนน หาคะแนนสูงสุด

ตัวอย่าง

[1,3,2,2,2,4,4,3,1] → 21 คะแนน

แนวทางแก้ปัญหา (DP 3 มิติ + Recursion)

• dp[i][j][k] = คะแนนสูงสุดจาก boxes[i..j] โดยมีกล่องสีเดียวกับ boxes[i] อยู่ด้านซ้าย k กล่อง (ติดกัน)
• Base: i > j → 0
• รวมกล่องติดกันสีเดียวกับ boxes[i] เข้า k
• Option 1: ลบ boxes[i] พร้อม k กล่องด้านซ้าย → (k+1)² + solve(i+1, j, 0)
• Option 2: หา x ใน (i+1..j] ที่ boxes[x] == boxes[i] แยกแก้ i+1..x-1 แล้วรวมกับ x..j (k+1)
• Memoization ป้องกันคำนวณซ้ำ

ตัวอย่างโปรแกรม

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

class Solution {
public:
    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];
        
        int ret = INT_MIN;
        for(; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++);
        ret = max(ret, (k + 1) * (k + 1) + solve(boxes, i + 1, j, 0, dp));
        
        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;
    }
    
    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));
}

Input

{1,3,2,2,2,4,4,3,1}

Output

21