As we have seen in previous weeks, a key step in analyzing a dynamic programming problem is selecting state variables that identify the subproblems to be solved. The solutions to these subproblems are stored in a table, which allows us to retrieve them efficiently when they come up again. So far, we have looked at problems with only one state variable. But the dynamic programming process also works when more than one state variable is required.
State variables are closely related to the table used to store subproblem solutions. We can think of them as indices into the table. So in last week’s problem, Longest Increasing Subsequence, we had a variable i storing a position in the input array. And we had an array dp where dp[i] stored the length of the longest increasing subsequence ending at position i.
When we select state variables, the goal is to select the minimum number of variables required to solve the problem. This has two advantages. In terms of storage resources, using one state variable means we only need $O(n)$ space to store the solution to every subproblem. If we designed our dp table for Longest Increasing Subsequence to store the length of the longest increasing subsequence starting at position i and ending at position j, we would need a two-dimensional array, or $O(n^2)$ space.
The other advantage of fewer state variables is a simpler solution. That doesn’t mean a solution that’s easier to invent. A solution with two variable might be more obvious, just as it’s easier to come up with brute force solution than an $O(n \log n)$ or $O(n)$ solution. But an extra state variable requires more complexity to keep track of. As with any LeetCode problem, the best approach is often to implement a more complex but more obvious solution first, and then optimize it. So you may start with multiple variables and discover that you can remove some of them.
For the LIS problem, we only need to store one solution for each ending position. In Coin Change, the only state variable required is amount, even though the input includes both an amount and an array of coins. But there are other problems that require more than one variable to identify a state. The additional variables may be explicitly identified in the problem statement, or you may come across them as you analyze the problem. There’s no step-by-step process to find these other variables. You just have to solve more problems and see a variety of patterns.
Next week, we’ll look at a well-known dynamic programming problem whose solution requires two state variables.
(Image credit: DALL·E 3)
For an introduction to this year’s project, see A Project for 2024.