Remove Boxes
Read editorial.


10 Prerequisite LeetCode Problems
“546. Remove Boxes” is a dynamic programming problem that requires a good understanding of DP with state definitions and recursion. To build up your understanding to tackle this problem, start with these problems:
“303. Range Sum Query  Immutable”: This problem introduces the concept of range queries which is useful in dynamic programming.
“304. Range Sum Query 2D  Immutable”: A variation of the previous problem, this introduces 2D range queries.
“322. Coin Change”: A classical DP problem where you need to find the fewest number of coins that you need to make up a certain amount.
“1143. Longest Common Subsequence”: This problem helps you understand how to define states in dynamic programming related to sequences.
“72. Edit Distance”: This problem is a good introduction to dynamic programming problems that involve making certain decisions at each state (insert, delete, replace in this case).
“198. House Robber”: This problem involves deciding between two options at each state, which is a good practice for decisionmaking in dynamic programming.
“516. Longest Palindromic Subsequence”: This problem helps understand how to deal with sequences and DP. It also relates to the manipulation of sequences like in “Remove Boxes”.
“647. Palindromic Substrings”: This problem also involves sequences and DP, and introduces the concept of palindromic sequences.
“139. Word Break”: This problem has you making decisions at each step in a sequence, which can be good practice for similar decisionmaking in the “Remove Boxes” problem.
“91. Decode Ways”: This problem involves making decisions based on current and previous state, which is a theme in many dynamic programming problems.


Problem Classification
You are 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 (i.e., composed of k boxes, k >= 1), remove them and get k * k points.
Return the maximum points you can get.
Example 1:
Input: boxes = [1,3,2,2,2,3,4,3,1] Output: 23 Explanation: [1, 3, 2, 2, 2, 3, 4, 3, 1] —> [1, 3, 3, 4, 3, 1] (33=9 points) —> [1, 3, 3, 3, 1] (11=1 points) —> [1, 1] (33=9 points) —> [] (22=4 points) Example 2:
Input: boxes = [1,1,1] Output: 9 Example 3:
Input: boxes = [1] Output: 1
Constraints:
1 <= boxes.length <= 100 1 <= boxes[i] <= 100
Language Agnostic Coding Drills
Drill 1: Understanding Data Types and Structures
 Create a list of integers and perform basic operations like insertion, deletion and modification.
 Create a function that accepts an integer as an argument and returns another integer.
Drill 2: Understanding Arithmetic Operations and Indexing
 Given a list of integers, write a function to calculate the sum of all elements in the list.
 Write a function that accepts a list and an index and returns the element at that index in the list.
Drill 3: Understanding Conditionals and Loops
 Write a function that loops over a list of integers and prints each one.
 Write a function that checks if a number exists in a given list of numbers.
Drill 4: Understanding Recursion
 Implement a recursive function that computes the factorial of a number.
 Implement a recursive function that finds the nth Fibonacci number.
Drill 5: Understanding the use of Decorators
 Write a simple decorator function that modifies the behavior of a function (like logging the function call or measuring execution time).
 Implement memoization in a recursive function using a decorator.
Drill 6: Understanding Dynamic Programming
 Implement a function that calculates the nth Fibonacci number using dynamic programming.
 Implement a function that solves the problem of minimum coin change using dynamic programming.
In each of the drills, it would be helpful to ensure the fundamentals of each concept are understood before proceeding to the next one. Once the concepts are well understood in isolation, they can be combined to solve more complex problems such as the box removal problem in the provided Python code.
Targeted Drills in Python
Understanding the use of data types and data structures: The code uses Lists, Integers, and Functions.
Understanding the use of decorators: The decorator
@lru_cache(None)
is used to add memoization to the functiondp
, which significantly speeds up recursive functions by storing the results of previous function calls.Understanding recursion: The function
dp
calls itself recursively.Understanding conditionals and loops: The function
dp
contains ifelse statements and a while loop and a for loop.Understanding indexing: The code uses indexing to manipulate and retrieve values from the List
boxes
.Understanding arithmetic operations: The code uses basic operations like addition, subtraction, and exponentiation.
Understanding the concept of dynamic programming: The problem is solved using a dynamic programming approach where the solution of the problem is calculated using the solutions of its subproblems.
These units can be arranged in increasing order of difficulty as follows:
 Understanding the use of data types and data structures
 Understanding arithmetic operations and indexing
 Understanding conditionals and loops
 Understanding recursion
 Understanding the use of decorators
 Understanding the concept of dynamic programming
The problemsolving approach is as follows:
Define a recursive function
dp
that takes in three parametersi
,j
, andk
.If
i
is greater thanj
, then no boxes are left, return 0.Calculate the points for the boxes between
i
andj
, inclusive, which have the same color as boxj
, plus the points for the rest of the boxes.Try all possible
m
so that the boxes in the range[m, j]
have the same color, and maximize the points.Use the decorator
lru_cache(None)
for memoization to avoid recalculating the points for the same range of boxes.Return the maximum points by calling the function
dp
with initial parameters.
Here are the Python coding drills.
Drill 1: Understanding Data Types and Structures
 Create a list of integers and perform basic operations like insertion, deletion and modification:


 Create a function that accepts an integer as an argument and returns another integer:


Drill 2: Understanding Arithmetic Operations and Indexing
 Given a list of integers, write a function to calculate the sum of all elements in the list:


 Write a function that accepts a list and an index and returns the element at that index in the list:


Drill 3: Understanding Conditionals and Loops
 Write a function that loops over a list of integers and prints each one:


 Write a function that checks if a number exists in a given list of numbers:


Drill 4: Understanding Recursion
 Implement a recursive function that computes the factorial of a number:


 Implement a recursive function that finds the nth Fibonacci number:


Drill 5: Understanding the use of Decorators
 Write a simple decorator function that modifies the behavior of a function (like logging the function call or measuring execution time):


 Implement memoization in a recursive function using a decorator:


Drill 6: Understanding Dynamic Programming
 Implement a function that calculates the nth Fibonacci number using dynamic programming:


 Implement a function that solves the problem of minimum coin change using dynamic programming:


These drills can be combined to create more complex solutions, such as the box removal problem in the Python code you provided earlier.