# Week 11: Dynamic Programming

### Intro

**Dynamic programming** is a method used to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions.

To implement dynamic programming:

**Identify Subproblems**: Divide the main problem into smaller, independent subproblems.**Store Solutions**: Solve each subproblem and store the solution.**Use Solutions**: Use the stored solutions to build up the solution to the main problem.

There are two approaches to dynamic programming:

**Top-Down (Memoization)**: Start from the top (main problem) and break it down into subproblems. Store the results of subproblems in a data structure (e.g., hash map) to avoid redundant computations.**Bottom-Up (Tabulation)**: Start from the bottom (subproblems) and build up the solution to the main problem. This approach is often more efficient in terms of space complexity.

Generally, you can solve a problem using either approach, but the choice depends on the problem and the constraints. During interviews, a good strategy is to first solve the problem using a simple recursive approach, then find a top-down dynamic programming solution. Ideally, the top-down approach will lead you to a bottom-up solution.

**Example**: Fibonacci Sequence

The Fibonacci sequence is a classic example of a problem that can be solved using dynamic programming. The sequence is defined as:

`1, 1, 2, 3, 5, 8, 13, 21, ...`

Each number in the sequence is the sum of the two preceding numbers. The naive recursive approach to calculating the nth Fibonacci number has exponential time complexity, as it recalculates the same subproblems multiple times.

```
/* Recursive approach */
int fib(int n) {
if (n <= 1){
return n;
}
return fib(n-1) + fib(n-2);
}
```

Diagram of the recursive calls for `fib(5)`

:

```
fib(5)
┌──────────────┴──────────────┐
fib(4) fib(3)
┌───────┴───────┐ ┌───────┴───────┐
fib(3) fib(2) fib(2) fib(1)
┌───┴────┐ ┌───┴───┐ ┌───┴───┐
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
┌───┴───┐
fib(1) fib(0)
```

For an input of 5, the recursive function calls `fib(3)`

twice, `fib(2)`

three times, and `fib(1)`

five times. To avoid this redundancy, we can use **memoization** (top-down DP) to store the results of subproblems.

```
/* Dynamic programming approach */
// Create a hash map to store the results of subproblems (memoization)
Map<Integer, Integer> memo = new HashMap<>();
int fib(int n) {
if (n <= 1) {
return n;
}
// Check if the result is already stored in the memo. If it is,
// don't recalculate, just return the stored result.
if (memo.containsKey(n)) {
return memo.get(n);
}
int result = fib(n-1) + fib(n-2); // calculate the subproblem
memo.put(n, result); // store the solution
return result;
}
```

New diagram of the call to `fib(5)`

:

```
fib(5)
┌──────┴──────┐
fib(4) fib(3)
┌─────┴─────┐
fib(3) fib(2)
┌───┴────┐
fib(2) fib(1)
┌───┴───┐
fib(1) fib(0)
```

By storing the results of subproblems in the `memo`

hash map, the function avoids redundant computations. The time complexity of this approach is linear, as each subproblem is solved only once.

Bottom-up dynamic programming can also be used to solve the Fibonacci sequence efficiently without recursion. This approach builds up the solution from the bottom by solving subproblems iteratively.

```
/* Bottom-up dynamic programming approach */
int fib(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1]; // create an array to store the results
dp[0] = 1; // base case
dp[1] = 1; // base case
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // calculate the next Fibonacci number
}
return dp[n]; // return the nth Fibonacci number
}
```

*Note*: The Fibonacci sequence is a simple example to illustrate dynamic programming and the bottom-up solution may seem obvious. However, for more complex problems, figuring out the top-down approach first can help you understand the subproblems and build up to a bottom-up solution.

### 1) Climbing Stairs

You are climbing a staircase. It takes `n`

steps to reach the top.

Each time you can either climb `1`

or `2`

steps. In how many distinct ways can you climb to the top?

**Example 1:**

```
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
```

**Example 2:**

```
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
```

*Constraints:*

`1 <= n <= 45`

### 2) Longest Increasing Subsequence

Given an integer array `nums`

, return the length of the longest strictly increasing subsequence.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

```
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
```

**Example 2:**

```
Input: nums = [0,1,0,3,2,3]
Output: 4
```

**Example 3:**

```
Input: nums = [7,7,7,7,7,7,7]
Output: 1
```

*Constraints:*

`1 <= nums.length <= 2500`

`-104 <= nums[i] <= 104`

### 3) Coin Change

You are given an integer array `coins`

representing coins of different denominations and an integer `amount`

representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`

.

You may assume that you have an infinite number of each kind of coin.

**Example 1:**

```
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
```

**Example 2:**

```
Input: coins = [2], amount = 3
Output: -1
```

**Example 3:**

```
Input: coins = [1], amount = 0
Output: 0
```

*Constraints:*

`1 <= coins.length <= 12`

`1 <= coins[i] <= 2^31 - 1`

`0 <= amount <= 10^4`

### 4) Burst Balloons

You are given n balloons, indexed from `0`

to `n - 1`

. Each balloon is painted with a number on it represented by an array `nums`

. You are asked to burst all the balloons.

If you burst the `ith`

balloon, you will get `nums[i - 1] * nums[i] * nums[i + 1]`

coins. If `i - 1`

or `i + 1`

goes out of bounds of the array, then treat it as if there is a balloon with a `1`

painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

**Example 1:**

```
Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
```

**Example 2:**

```
Input: nums = [1,5]
Output: 10
```

*Constraints:*

`n == nums.length`

`1 <= n <= 300`

`0 <= nums[i] <= 100`