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

# 难题，过于难，dp的第三维不太好理解but it is the key
# 直接看https://github.com/wisdompeak/LeetCode/tree/master/DFS/546.Remove-Boxes
class Solution:
    def bt(self, boxes, l, r, k):
        if l > r:
            return 0

        if self.dp[l][r][k] != 0:
            return self.dp[l][r][k]

        i = r
        count = k  # Note, 初始化为k而不是0，因为要往右累加
        # 先找最右边那个和boxes[r]相同的元素形成的一个subarray group
        while i >= l and boxes[i] == boxes[r]:
            i -= 1
            count += 1

        # 假设最右边的那个group不和其它任何组合。它单独被remove
        self.dp[l][r][k] = self.bt(boxes, l, i, 0) + count * count

        j = i
        for j in range(i, l - 1, -1):
            # 只要和boxes[r]不同，就一视同仁continue
            if boxes[j] != boxes[r]:
                continue

            if boxes[j] == boxes[r] and boxes[j + 1] == boxes[r]:
                j -= 1
                continue
                # count += 1 

            self.dp[l][r][k] = max(
                self.dp[l][r][k],
                self.bt(boxes, l, j, count) + self.bt(boxes, j + 1, i, 0),
            )

        return self.dp[l][r][k]


    def removeBoxes(self, boxes):
        n = len(boxes)
        self.dp = [[[0 for _1 in range(100)] for _2 in range(n)] for _3 in range(n)]
        # dp[l][r][k]代表[l..r]这个both inclusive的区间，而且右边还有可以组合元素的个数
        return self.bt(boxes, 0, n - 1, 0)

27600