<p>You are given several <code>boxes</code> with different colors represented by different positive numbers.</p>

<p>You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of <code>k</code> boxes, <code>k &gt;= 1</code>), remove them and get <code>k * k</code> points.</p>

<p>Return <em>the maximum points you can get</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> boxes = [1,3,2,2,2,3,4,3,1]
<strong>Output:</strong> 23
<strong>Explanation:</strong>
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----&gt; [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----&gt; [1, 3, 3, 3, 1] (1*1=1 points) 
----&gt; [1, 1] (3*3=9 points) 
----&gt; [] (2*2=4 points)
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> boxes = [1,1,1]
<strong>Output:</strong> 9
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> boxes = [1]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= boxes.length &lt;= 100</code></li>
	<li><code>1 &lt;= boxes[i]&nbsp;&lt;= 100</code></li>
</ul>

// https://leetcode.com/problems/remove-boxes/

static const auto s_initialize = [] { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return nullptr; }();

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        return removeBoxes_v1(boxes); // [120, 129] ms, 34.54 MB.
    }


private:
    // method 1. DP.
    //    Approach 2: Top-Down Dynamic Programming
    // O( n^4 ); O( n^3 ).
    int removeBoxes_v1(const vector<int>& boxes) {
        const int n = static_cast<int>(boxes.size());
        // vvvDp[i][j][k]:
        //    for the subarray "boxes[i..(i+j)]",
        //    there are k additional "boxes[(i+j)]" appended at the right of "boxes[i..(i+j)]",
        //    the max points it can get.
        std::vector< std::vector< std::vector<int> > > vvvDp( n );
        for (int i = 0; i < n; ++i) {
            auto& vvDp = vvvDp[i];
            const int cnt = n - i;
            vvDp.resize(cnt);
            for (int j = 0; j < cnt; ++j) {
                auto& vDp = vvDp[j];
                vDp.resize(n - i - j, -1);
            }
            vvDp[0][0] = 1;
        }
        //
        std::function< int(const int, int, int) > tDp;
        tDp = [=, &tDp, &boxes, &vvvDp] (const int i, int j, int k) -> int {
            const int v = boxes[i + j];
            while (0 < j && v == boxes[i + j - 1]) {
                --j;
                ++k;
            }
            int tMaxPnts = vvvDp[i][j][k];
            if (-1 == tMaxPnts) {
                tMaxPnts = (0 < j ? tDp(i, j - 1, 0) : 0) + ( (k + 1) * (k + 1) );
                for (int t = 0; t < j; ++t) {
                    if (v == boxes[i + t]) {
                        const int tPnts = tDp(i, t, k + 1) + (t + 1 < j ? tDp(i + t + 1, j - t - 2, 0) : 0);
                        tMaxPnts = std::max(tMaxPnts, tPnts);
                    }
                }
                vvvDp[i][j][k] = tMaxPnts;
            }
            return tMaxPnts;
        };
        return tDp(0, n - 1, 0);
    }

};

22415