## Solving a Question with Dynamic Programming

This page breaks down how to solve a question with dynamic programming into a series of steps which ultimately leads to the "bottom-up" solution to the problem.

- Find the Recurrence Relation
- Identify the Base Case(s)
- Write the Recursive Solution
- Add Memoization
- Convert to "Bottom-Up" DP
- Further Optimization

###### DESCRIPTION (credit Leetcode.com)

You're a treasure hunter in a neighborhood where houses are arranged in a row, and each house contains a different amount of treasure. Your goal is to collect as much treasure as possible, but there's a catch: if you collect treasure from two adjacent houses, it triggers a neighborhood-wide alert, ending your hunt immediately.

Given an array treasure of non-negative integers, where each integer represents the amount of treasure in a house, write a function to return the maximum amount of treasure you can collect without triggering any alarms.

**Example 1:**
Input: treasure = : [3, 1, 4, 1, 5]
Best Haul: 12

Explanation: Collect from houses 0, 2, and 4 for a total of 3 + 4 + 5 = 12.

#### Why Dynamic Programming?

Let's first touch on why this question is a good candidate for dynamic programming.

Recall from the Fundamentals section that a problem is a good candidate for dynamic programming if:

- It has optimal substructure (it can be solved using recursion)
- It has overlapping subproblems (the same recursive call is made multiple times)

So let's break down why this problem has both of these properties.

##### Optimal Substructure

This problem has optimal substructure because the optimal solution for the first i houses can be calculated using the optimal solutions for the first i - 2 and i - 1 houses.

Say we are trying to calculate the optimal solution for the first 6 houses in array treasure below:

If we already know the optimal solution for the first 5 houses is 12:

And the optimal solution for the first 4 houses is 7:

Then we have two choices for including house 6:

We can choose to *take* from house 6 by adding its value to the optimal solution for 4 houses, which in this case gives us 9:

Or we can choose to *skip* house 6 by using the optimal solution for 5 houses, which is 12:

By taking the maximum of those values, we can calculate the optimal solution for the first 6 houses, which is 12.

We can then calculate the optimal solution for 7 houses in the same way, by using the optimal solution for 5 houses (which allows us to take from house 7), and 6 houses (which allows us to skip house 7).

##### Overlapping Subproblems

We can imagine that as our treasure array grows, we will end up using the optimal solution for the same subproblems multiple times. For example, we use the optimal solution for the first 5 houses to calculate both the optimal solution for the first 6 houses and the optimal solution for the first 7 houses.

We'll get a better visual of the overlapping subproblems in Step 3, but for now, we've identified this is a good candidate for dynamic programming because of the overlapping subproblems and optimal substructure properties.

We can now move to the first step:

### 1. Identify the Recurrence Relation

We can formalize the optimal substructure from above by defining a **recurrence relation** for the problem. A recurrence relation describes the answer to our problem in terms of answers to the same problem with smaller inputs.

We saw from above that the optimal solution for the first i houses can be calculated using the optimal solutions for the first i - 2 and i - 1 houses.

Let dp(i) be the optimal solution for the first i houses. Then our recurrence relation is:

dp(i) = max(dp(i - 1), dp(i - 2) + treasure[i - 1])

**Make sure you are clear as to what the recurrence relation represents in terms of the input and the problem**. Having a clear, consistent definition of what the recurrence relation represents will help you with every step of this process.

In this case, dp(i) refers to the optimal solution (most amount treasure) that can be collected from the *first i houses* of treasure, which is why we use i - 1 to index into treasure. (In other words, to calculate the optimal solution for the first 6 houses, we need to consider treasure[5], since treasure is 0-indexed.)

### 2. Identify the base case(s)

By now, we have a clear understanding of what our recurrence relation represents. We should use that understanding to identify the base case(s) for our problem.

The base cases are the inputs for which we know the answer without having to use the recurrence relation. They are typically the smallest possible values for our parameters.

In this case:

- If we have 0 houses, we can't collect any treasure, so dp(0) = 0.
- If we have 1 house, we can only collect the treasure from the first house, so dp(1) = treasure[0].

### 3. Write the Recursive Solution

Combine the recurrence relation and the base case(s) to write the recursive solution. This involves introducing a helper function with the same signature as the recurrence relation we defined in Step 1.

def rob(treasure):if not treasure:return 0def rob_helper(i):if i == 0:return 0if i == 1:return treasure[0]skip = rob_helper(i - 1)take = rob_helper(i - 2) + treasure[i - 1]return max(skip, take)return rob_helper(len(treasure))

**Overlapping Subproblems**

With the recursive solution written out, we can clearly see the overlapping subproblems by visualizing the call tree of our recursive function. The call tree shows the function calls made when treasure has 6 houses:

Our recursive function has an exponential time complexity of O(2n), where n is the length of the treasure array. We can make it much more efficient by adding memoization.

### 4. Add Memoization

With our recursive solution written, adding memoization is a three-step process:

- Initialize an empty dictionary to store the results of recursive calls. Eventually the keys of the dictionary will be the inputs to the recursive function, and the values will be the results of the recursive function.

Now, inside the body of the recursive function:

- If the input to the recursive function is in the memoization dictionary, return the value stored in the dictionary.
**Make sure you do this before making any recursive calls**. - If the input is not in the dictionary, calculate the value via recursion and store it in the dictionary before the return statement.

def rob(treasure):if not treasure:return 0# initialize memoization dictionarymemo = {}def rob_helper(i):# base casesif i == 0:return 0if i == 1:return treasure[0]# check and return from memo# BEFORE making any recursive callsif i in memo:return memo[i]# recurrence relationskip = rob_helper(i - 1)take = rob_helper(i - 2) + treasure[i - 1]result = max(skip, take)# store result in memo before returningmemo[i] = resultreturn resultreturn rob_helper(len(treasure))

Adding memoization reduces the time complexity of our solution to O(n), where n is the length of the treasure array. This is because we only need to calculate the optimal solution for each house once. When we need to calculate it again, we can just look it up in the memoization dictionary in O(1) time.

### 5. Convert to "Bottom-Up" DP

Finally, we can convert our memoized recursive solution to a bottom-up dynamic programming solution. A "bottom-up" dynamic programming solution uses iteration to build up to the final solution from base cases.

Step 1: Initialize an array to store the results of the subproblems.

In this case, dp[i] will represent the optimal solution for the first i houses, which means we need an array of size len(treasure) + 1 to store the results of the subproblems.

In other words, if we are solving for an array size of 6, we need an array of size 7 to store the results of the subproblems for 0 to 6 houses. The final answer will be stored in dp[6].

Step 2: Fill in the base cases in the array.

In this case, dp[0] = 0 and dp[1] = treasure[0]. In other words, the optimal solution for 0 houses is 0, and the optimal solution for 1 house is the treasure at the first house.

Step 3: Start iterating to fill in the rest of the array, up to and including the final answer at dp[len(treasure)]. Use the recurrence relation to calculate each value.

def rob(treasure):if not treasure:return 0# initialize dp arraydp = [0] * (len(treasure) + 1)# fill in base cases (dp[0] = 0 already)dp[1] = treasure[0]# iterate to fill in the rest of the arrayfor i in range(2, len(treasure) + 1):# fill in dp[i] using the recurrence relationtake = dp[i - 2] + treasure[i - 1]skip = dp[i - 1]dp[i] = max(take, skip)return dp[len(treasure)]

### 6. Further Optimization

For this question, there is room for further optimization. We can see that we only need to keep track of the two most recent values of dp to calculate the next value. In other words, once we've obtained dp[4], we no longer need dp[0], dp[1], or dp[2] for the rest of the calculation.

This means we don't need to store the entire dp array, just the last two values, which we use to calculate the next value. This can reduce the space complexity of our solution from O(n) to O(1).

def rob(treasure):if not treasure:return 0prev, curr = 0, treasure[0]for i in range(2, len(treasure) + 1):# calculate the next value of dptake = prev + treasure[i - 1]skip = currprev, curr = curr, max(take, skip)return curr

### Common Mistakes

**It's important to keep the variables you use in your code consistent with how you defined the subproblems in the recurrence relation.** This will help you avoid off-by-one errors and other bugs.

For example, we could have alternatively defined dp(i) to represent the optimal solution of all houses up to the ith-index in the treasure array. So dp(0) would represent the optimal solution for the first house, dp(1) would represent the optimal solution for the first two houses, and so on.

This simple change in definition has many downstream effects:

def rob(treasure):if not treasure:return 0if len(treasure) == 1:return treasure[0]# Initialize dp arraydp = [0] * len(treasure)# Base casesdp[0] = treasure[0]dp[1] = max(treasure[0], treasure[1])# Fill dp arrayfor i in range(2, len(treasure)):dp[i] = max(dp[i-1], dp[i-2] + treasure[i])return dp[len(treasure) - 1]

- The base cases change: dp[0] = treasure[0] and dp[1] = max(treasure[0], treasure[1])
- The recurrence relation is different: dp(i) = max(dp(i - 1), dp(i - 2) + treasure[i])
- The bounds of the iteration change.

The fact that a simple change in definition can have downstream effects in so many parts of the code is why it's so easy to make off-by-one errors or index out of bounds errors as you work through dynamic programming problems.

**So remember: the more clearly you can define your subproblems in terms of the inputs and the problem, the easier it is to keep everything consistent.** Keep this in mind as you work through dynamic programming problems that follow.

Loading comments...