Framework for DP Problems

Framework for DP Problems

The Framework

1. A function or data structure that will compute/contain the answer to the problem for every given state.

2. A recurrence relation to transition between states.

3. Base cases, so that our recurrence relation doesn't go on infinitely.

Approach: Top-down and Bottom-up

Bottom-up (Tabulation)

// Pseudocode example for bottom-up

F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
    F[i] = F[i - 1] + F[i - 2]

Top-down (Memoization)

// Pseudocode example for top-down

memo = hashmap
Function F(integer i):
    if i is 0 or 1: 
        return i
    if i doesn't exist in memo:
        memo[i] = F(i - 1) + F(i - 2)
    return memo[i]

Steps to convert top-down into bottom-up

1. Start with a completed top-down implementation.

2. Initialize an array $\text{dp}$ that is sized according to your state variables. For example, let's say the input to the problem was an array $\text{nums}$ and an integer $\text{k}$ that represents the maximum number of actions allowed. Your array $\text{dp}$ would be 2D with one dimension of length $\text{nums.length}$ and the other of length $\text{k}$. The values should be initialized as some default value opposite of what the problem is asking for. For example, if the problem is asking for the maximum of something, set the values to negative infinity. If it is asking for the minimum of something, set the values to infinity.

3. Set your base cases, same as the ones you are using in your top-down function. Recall in House Robber, $\text{dp(0) = nums[0]}$ and $\text{dp(1) = max(nums[0], nums[1])}$. In bottom-up, $\text{dp[0] = nums[0]}$ and $\text{dp[1] = max(nums[0], nums[1])}$.

4. Write a for-loop(s) that iterate over your state variables. If you have multiple state variables, you will need nested for-loops. These loops should start iterating from the base cases.

5. Now, each iteration of the inner-most loop represents a given state, and is equivalent to a function call to the same state in top-down. Copy the logic from your function into the for-loop and change the function calls to accessing your array. All $\text{dp(...)}$ changes into $\text{dp[...]}$.

6. We're done! $\text{dp}$ is now an array populated with the answer to the original problem for all possible states. Return the answer to the original problem, by changing $\text{return dp(...)}$ to $\text{return dp[...]}$.

When to Use DP

The first characteristic

that is common in DP problems is that the problem will ask for the optimum value (maximum or minimum) of something, or the number of ways there are to do something. For example:

• What is the minimum cost of doing...

• What is the maximum profit from...

• How many ways are there to do...

• What is the longest possible...

• Is it possible to reach a certain point...

The second characteristic

that is common in DP problems is that future "decisions" depend on earlier decisions. Deciding to do something at one step may affect the ability to do something in a later step. This characteristic is what makes a greedy algorithm invalid for a DP problem - we need to factor in results from previous decisions.

What is Dynamic Programming?

Dynamic Programming (DP) is a programming paradigm that can systematically and efficiently explore all possible solutions to a problem. As such, it is capable of solving a wide variety of problems that often have the following characteristics:

1. The problem can be broken down into "overlapping subproblems" - smaller versions of the original problem that are re-used multiple times.
2. The problem has an "optimal substructure" - an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem.

Iteration in the recurrence relation

---

In all the problems we have looked at so far, the recurrence relation is a static equation - it never changes. Recall Min Cost Climbing Stairs. The recurrence relation was:

$\text{dp(i)} = \min( \text{dp(i - 1) + cost[i - 1], dp(i - 2) + cost[i - 2]})$

because we are only allowed to climb 1 or 2 steps at a time. What if the question was rephrased so that we could take up to $\text{k}$ steps at a time? The recurrence relation would become dynamic - it would be:

$\text{dp(i)} = \min( \text{dp(j) + cost[j])}$ for all $\text{(i - k)} \leq \text{j} < \text{i}$

We would need iteration in our recurrence relation.

This is a common pattern in DP problems, and in this chapter, we're going to take a look at some problems using the framework where this pattern is applicable. While iteration usually increases the difficulty of a DP problem, particularly with bottom-up implementations, the idea isn't too complicated. Instead of choosing from a static number of options, we usually add a for-loop to iterate through a dynamic number of options and choose the best one.

State Transition by Inaction

---

This is a small pattern that occasionally shows up in DP problems. Here, "doing nothing" refers to two different states having the same value. We're calling it "doing nothing" because often the way we arrive at a new state with the same value as the previous state is by "doing nothing" (we'll look at some examples soon). Of course, a decision making process needs to coexist with this pattern, because if we just had all states having the same value, the problem wouldn't really make sense ($\text{dp(i) = dp(i - 1)} ?$) It is just that if we are trying to maximize or minimize a score for example, sometimes the best option is to "do nothing", which leads to two states having the same value. The actual recurrence relation would look something like $\text{dp(i, j) = max(dp(i - 1, j), ...)}$.

Usually when we "do nothing", it is by moving to the next element in some input array (which we usually use $\text{i}$ as a state variable for). As mentioned above, this will be part of a decision making process due to some restriction in the problem. For example, think back to House Robber: we could choose to rob or not rob each house we were at. Sometimes, not robbing the house is the best decision (because we aren't allowed to rob adjacent houses), then $\text{dp(i) = dp(i - 1)}$.

In the next article, we'll use the framework to solve a problem with this pattern.

State Reduction

---

Note: state reductions for space complexity usually only apply to bottom-up implementations, while improving time complexity by reducing the number of state variables applies to both implementations.

When it comes to reducing state variables, it's hard to give any general advice or blueprint. The best advice is to try and think if any of the state variables are related to each other, and if an equation can be created among them. If a problem does not require iteration, there is usually some form of state reduction possible.

Whenever you notice that values calculated by a DP algorithm are only reused a few times and then never used again, try to see if you can save on space by replacing an array with some variables. A good first step for this is to look at the recurrence relation to see what previous states are used. For example, in Fibonacci, we only refer to the previous two states, so all results before $\text{n - 2}$ can be discarded.

Counting DP

---

Most of the problems we have looked at in earlier chapters ask for either the maximum, minimum, or longest of something. However, it is also very common for a DP problem to ask for the number of distinct ways to do something. In fact, one of the first examples we looked at did this - recall that Climbing Stairs asked us to find the number of ways to climb to the top of the stairs.

Another term used to describe this class of problems is "counting DP".

What are the differences with counting DP? With the maximum/minimum problems, the recurrence relation typically involves a $\text{max()}$ or $\text{min()}$ function. This is true for all types of problems we have looked at - iteration, multi-dimensional, etc. With counting DP, the recurrence relation typically just sums the results of multiple states together. For example, in Climbing Stairs, the recurrence relation was $\text{dp(i) = dp(i - 1) + dp(i - 2)}$. There is no $\text{max()}$ or $\text{min()}$, just addition.

Another difference is in the base cases. In most of the problems we have looked at, if the state goes out of bounds, the base case equals $\text{0}$. For example, in the Best Time to Buy and Sell Stock questions, when we ran out of transactions or ran out of days to trade, we returned $\text{0}$ because we can't make any more profit. In Longest Common Subsequence, when we run out of characters for either string, we return $\text{0}$ because the longest common subsequence of any string and an empty string is $\text{0}$. With counting DP, the base cases are often not set to $\text{0}$. This is because the recurrence relation usually only involves addition terms with other states, so if the base case was set to $\text{0}$ then you would only ever add $\text{0}$ to itself. Finding these base cases involves some logical thinking - for example, when we looked at Climbing Stairs - we reasoned that there is $\text{1}$ way to climb to the first step and $\text{2}$

$\text{2}$ ways to climb to the second step. 

Kadane's Algorithm

---

Kadane's Algorithm is an algorithm that can find the maximum sum subarray given an array of numbers in $O(n)$ time and $O(1)$ space. Its implementation is a very simple example of dynamic programming, and the efficiency of the algorithm allows it to be a powerful tool in some DP algorithms. If you haven't already solved Maximum Subarray, take a quick look at the problem before continuing with this article - Kadane's Algorithm specifically solves this problem.

Kadane's Algorithm involves iterating through the array using an integer variable $\text{current}$, and at each index $\text{i}$, determines if elements before index $\text{i}$ are "worth" keeping, or if they should be "discarded". The algorithm is only useful when the array can contain negative numbers. If $\text{current}$ becomes negative, it is reset, and we start considering a new subarray starting at the current index.

Pseudocode for the algorithm is below:

// Given an input array of numbers "nums",
1. best = negative infinity
2. current = 0
3. for num in nums:
    3.1. current = Max(current + num, num)
    3.2. best = Max(best, current)

4. return best

Line 3.1 of the pseudocode is where the magic happens. If $\text{current}$ has become less than 0 from including too many or too large negative numbers, the algorithm "throws it away" and resets.

While usage of Kadane's Algorithm is a niche, variations of Kadane's Algorithm can be used to develop extremely efficient DP algorithms. Try the next two practice problems with this in mind. No framework hints are provided here as implementations of Kadane's Algorithm do not typically follow the framework intuitively, although they are still technically dynamic programming (Kadane's Algorithm utilizes optimal sub-structures - it keeps the maximum subarray ending at the previous position in $\text{current}$).