Here are some advanced DP concepts that haven’t been covered in the introduction page. We seek to figure out how we can make out DP solutions work better.

Going Faster

There are some techniques we can use to make our DP solution better. We will consider some strategies here.

Change the Recurrence

The idea is to come up with a recurrence where the number of sub-problems is minimized.

The idea is often to let the recurrence capture multiple references to sub-problems instead of hard-coding them. Refer to the Unbounded Knapsack Problem for an example: Going Faster.

To be able to do this, you need to grasp the problem at a high level. Once you understand the structure of the problem, see what can be changed and what is fixed. This will bring you towards a solution.

Another way to see how we can change the recurrence may come from examining the solution space. Then we determine what the most efficient way to traverse the solution space is.

Here are some questions you can ask to come up with improvements:

• Ask whether the state is too detailed.
• Ask whether two dimensions can be collapsed into one.
• Ask whether the transition can be re-expressed as a window, a monotone choice, a line, or a divide-and-conquer split.
• Ask whether a hidden invariant lets you avoid checking every previous state.

Here is how we can address these issues once we have identified them:

Compress State Space

If there is information that is redundant, we can capture it using one variable instead of needing two. To apply this, identify dependent variables that can be derived or aggregated; replace them with smaller descriptors (e.g., parity, min/max, counts).

<aside> 💡

A hack to see how we can compress state space is by drawing it out and observing the DAG that forms. Look at what states are used and whether redundant information can be eliminated.

</aside>

If we cannot reduce the number of variables at least we can reduce their ranges. Here is an example:

Consider this problem:

You have n items, each with a weight w[i] and value v[i]. Your knapsack has capacity W. Maximize total value without exceeding W. Constraints: n ≤ 100, v[i] ≤ 100, but W ≤ 10^9.

The standard formulation is: