Remove Boxes: กำจัดกล่องเพื่อคะแนนสูงสุดใน C++

ปัญหา

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

ตัวอย่าง: [1,3,2,2,2,4,4,3,1] → 21

แนวคิด: 3D DP (Interval DP + Extra State)

State

dp[i][j][k] = คะแนนสูงสุดจากกล่อง i..j โดยมีกล่องสีเดียวกับ boxes[i] ติดมาจากด้านซ้ายอีก k กล่อง

Key Insight: การรวมกล่องสีเดียวที่แยกกัน → ได้คะแนนมากกว่า (เพราะ (a+b)² > a² + b²)

Recurrence

1. รวมกล่องติดกันด้านหน้า: ขยับ i ข้ามกล่องสีเดียวกัน รวมเข้า k
2. ตัวเลือก 1: กำจัดกลุ่มแรกทันที: (k+1)² + dp[i+1][j][0]
3. ตัวเลือก 2: รวมกับกล่องสีเดียวกันภายหลัง: หา m ∈ (i+1..j] ที่ boxes[m] == boxes[i]

   dp[i+1][m-1][0] + dp[m][j][k+1]
       

   กำจัดกลางก่อน แล้วรวมกล่อง i กับ m

Base Case

i > j → 0

โค้ด 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];
        
        // รวมกล่องติดกันด้านหน้าที่สีเดียว
        int orig_i = i, orig_k = k;
        while (i + 1 <= j && boxes[i + 1] == boxes[i]) {
            i++; k++;
        }
        
        int ret = INT_MIN;
        // Option 1: กำจัดกลุ่มนี้ทันที
        ret = max(ret, (k + 1) * (k + 1) + solve(boxes, i + 1, j, 0, dp));
        
        // Option 2: รวมกับกล่องสีเดียวกันภายหลัง
        for (int m = i + 1; m <= j; m++) {
            if (boxes[m] == boxes[i]) {
                ret = max(ret, 
                    solve(boxes, i + 1, m - 1, 0, dp) + 
                    solve(boxes, m, j, k + 1, dp)
                );
            }
        }
        
        return dp[orig_i][j][orig_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;
}

การทำงานตัวอย่าง

[1, 3, 2,2,2, 4,4, 3, 1]
→ กำจัด 2,2,2 (9 pts) → [1, 3, 4,4, 3, 1]
→ กำจัด 4,4 (4 pts)   → [1, 3, 3, 1]
→ กำจัด 3,3 (4 pts)   → [1, 1]
→ กำจัด 1,1 (4 pts)   → []
Total = 9+4+4+4 = 21

ความซับซ้อน

• Time: O(n⁴) worst case (n ≤ 100 ในโจทย์ต้นฉบับ)
• Space: O(n³)

หมายเหตุ: n=100 → n⁴ = 10⁸ อาจต้องเพิ่มประสิทธิภาพเพิ่ม (เช่น pruning)

Input / Output

Input:  {1,3,2,2,2,4,4,3,1}
Output: 21