Problem

Given several boxes with different colors represented by different positive numbers.
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 (composed of k boxes, k >= 1), remove them and get k*k points.
Find the maximum points you can get.

Example 1:
Input:

Output:

Explanation:

[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 points)
----> [1, 3, 3, 3, 1] (1*1=1 points)
----> [1, 1] (3*3=9 points)
----> [] (2*2=4 points)


Note: The number of boxes n would not exceed 100.

Solution: Recursion + Memorization

Use dp[l][r][k] to denote the max score of subarray box[l] ~ box[r] with k boxes after box[r] that have the same color as box[r]

box[l], box[l+1], …, box[r], box[r+1], …, box[r+k]

e.g. “CDABACAAAAA”

dp[2][6][4] is the max score of [ABACA] followed by [AAAA]
dp[2][6][3] is the max score of [ABACA] followed by [AAA]

base case: l > r, empty array, return 0.
Transition:
dp[l][r][k] = max(dp[l][r-1][0] + (k + 1)*(k + 1),  # case 1
dp[l][i][k+1] + dp[i+1][r-1][0])  # case 2
# "ABACA|AAAA"
# case 1: dp("ABAC") + score("AAAAA") drop j and the tail.
# case 2: box[i] == box[r], l <= i < r, try all break points
# max({dp("A|AAAAA") + dp("BAC")}, {dp("ABA|AAAAA") + dp("C")})

Time complexity: O(n^4)

Space complexity: O(n^3)

C++

Optimized

Use a HashTable to replace the 3D DP array since the DP array could be sparse when many consecutive boxes are the same color.

Related Problems

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode