<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>

class Solution
{
public:
    int removeBoxes(std::vector<int> & boxes)
    {
        auto n = static_cast<const int>(boxes.size());
        std::vector dp(n + 2, std::vector(n + 2, std::vector<int>(n + 2, -1)));
        return f(boxes, 0, n - 1, 0, dp);
    }

private:
    int f(const std::vector<int> & boxes, 
           int i, 
           int j, 
           int pl,
           std::vector<std::vector<std::vector<int>>> & dp)
    {
        if (j < i)
        {
            return 0;
        }

        // Max score to remove boxes[i...j], 
        // with pl predecessors whose colors are same as boxes[i].
        if (dp[i][j][pl] != -1)
        {
            return dp[i][j][pl];
        }

        int s = i;

        while (s < j && boxes[i] == boxes[s + 1])
        {
            ++s;
        }

        // [  ] X X X X Y ... X ... ?
        //  pl  i     s       k     j

        int cnt = pl + s - i + 1;
        int best = cnt * cnt + f(boxes, s + 1, j, 0, dp);

        for (int k = s + 2; k <= j; ++k)
        {
            if (boxes[k] == boxes[i] && boxes[k] != boxes[k - 1])
            {
                best = std::max(best, f(boxes, s + 1, k - 1, 0, dp) + f(boxes, k, j, cnt, dp));
            }   
        }

        return dp[i][j][pl] = best;
    }
};
81760