# A.5: Dynamic Programming

## Learning Objectives

Dynamic programming (DP) problems are a subset of recursion problems that involve caching intermediate calculations to avoid repeated calculations

DP problems often involve "take or don't take" logic in each recursive call, which results in repeated calculations without caching

DP problems are not the most commonly seen interview problems (less common at most SWE jobs), and Rocket recommends being comfortable with prior algorithm topics before spending too much time on DP

## Introduction

Dynamic programming allows us to optimise recursive solutions by "caching" (i.e. storing) intermediate calculations to minimise repeated and redundant recursive calls.

The first 40 minutes of the below video visually explain the premise behind dynamic programming and why it is powerful. The remainder of the video walks through DP solutions to other problems, which we do not need to review right now.

## Take or Don't Take

Many dynamic programming problems involve "take or don't take" logic, where we will need to choose an optimal set of values from a collection (e.g. array) with constraints such as no two adjacent values can be in the solution.

For example, given an input array, our objective might be to find the maximum sum of chosen values in the array where we cannot choose adjacent values.

This problem is not the most straightforward because we cannot adopt a "greedy" solution by always choosing the largest numbers we see. Doing so may give us a suboptimal solution. For example, if the input array were `[2, 4, 3]`

, the optimal solution would be to pick `2`

and `3`

, but if we had just chosen the largest of the first 2 numbers we looked at, we would have picked 4.

This is where recursion can help us, and dynamic programming can help optimise. Let's call this problem `maxSumNoAdjacent`

. My code might look like the following.

Notice in the final line of the code we return the maximum of values when we "take or don't take".

## Exercises

### Part 1

Please fork starter code Repl and attempt solutions there. Feel free to compare with reference solutions after attempting each problem. Conway and Catalan problems are optional. Have fun!

### Part 2

Climbing Stairs (LeetCode)

### Part 3

Min Cost Climbing Stairs (LeetCode)

### Part 4

House Robber (LeetCode)

### More Comfortable

Maximum Points You Can Obtain From Cards (LeetCode)

Minimum Operations to Reduce X to Zero (LeetCode)

Coin Change (HackerRank, LeetCode)

## Further Reading

Video solution to Longest Common Subsequence, a DP problem that involves storing intermediate calculations in a table with dimensions

`m`

by`n`

, where`m`

is the length of 1 input word and`n`

is the length of the other.

Last updated