CSE 373 WI25 Section 9

Dynamic Programming

Created by Sravani, best 373 TA ever

Agenda

• Announcements

​

• Dynamic Programming

​

​

​

​

Announcements

• P4 due 3/14!!

Microteach: Dynamic Programming

Min Cost to Climb Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

​

You can either start from the step with index 0, or the step with index 1.

​

Return the minimum cost to reach the top of the floor.

​

Example:

Input: cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

​

​

Explanation: You will start at index 0.

- Pay 1 and climb two steps to reach index 2.

- Pay 1 and climb two steps to reach index 4.

- Pay 1 and climb two steps to reach index 6.

- Pay 1 and climb one step to reach index 7.

- Pay 1 and climb two steps to reach index 9.

- Pay 1 and climb one step to reach the top.

The total cost is 6.

How would we do this currently? Recursion

Lets say minimumCost(i) represents the minimum cost to reach the ith step.

​

The base cases for this function will be

minimumCost(0) = minimumCost(1) = 0

since we are allowed to start on either step 0 or step 1.

​

For any other step i, we can write this as a recurrence: (Fibonacci from lect.)

minimumCost(i) = min(cost[i - 1] + minimumCost(i - 1),

cost[i - 2] + minimumCost(i - 2))

T(i) = T(i - 1) + T(i - 2)

​

Why is this inefficient?

To figure out what the value of minimumCost(5), we call minimumCost(3) and minimumCost(4).

minimumCost(4) then calls minimumCost(3) again.

Both the minimumCost(3) calls will call minimumCost(2), on top of another minimumCost(2) call from minimumCost(4).

Thats a LOT of repeated calculations!

​

The fix!

Dynamic Programming!!

​

Two different kinds of DP:

1. Top-Down
2. Bottom-Up

​

Top-Down

Take a recursive solution, figure out what solutions should be “saved”, and use those instead of calling the function again when they exist!

For example, if we calculate minimumCost(3) once, why should we calculate it again? Instead of going through the entire subtree every time we want to calculate minimumCost(3), we will store the value of minimumCost(3) after calculating it the first time, and refer to that instead.

​

This is what memoization is - caching "expensive" function calls to avoid duplicate computations.

We can use a hash map for the memoization, where each key will have the value minimumCost(key).

​

Top-Down Continued

Algorithm

• Define a hash map memo, where memo[i] represents the minimum cost of reaching the ith step.
• Define a function minimumCost, where minimumCost(i) will determine the minimum cost to reach the ith step.
• In our function minimumCost, first check the base cases: return 0 when i == 0 or i == 1. Next, check if the argument i has already been calculated and stored in our hash map memo. If so, return memo[i]. Otherwise, use the recurrence relation to calculate memo[i], and then return memo[i].
• If we already have the value, we won’t recalculate it!
• Call and return minimumCost(cost.length).

​

Top-Down

class Solution {

private HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();

public int minCostClimbingStairs(int[] cost) {

return minimumCost(cost.length, cost);

}

private int minimumCost(int i, int[] cost) {

// Base case, we are allowed to start at either step 0 or step 1

if (i <= 1) {

return 0;

}

// Check if we have already calculated minimumCost(i)

if (memo.containsKey(i)) {

return memo.get(i);

}

// If not, cache the result in our hash map and return it

int downOne = cost[i - 1] + minimumCost(i - 1, cost);

int downTwo = cost[i - 2] + minimumCost(i - 2, cost);

memo.put(i, Math.min(downOne, downTwo));

return memo.get(i);

}

}

​

Define a hash map memo, where memo[i] represents the minimum cost of reaching the ith step.

Define a function minimumCost, where minimumCost(i) will determine the minimum cost to reach the ith step.

​

In our function minimumCost, first check the base cases: return 0 when i == 0 or i == 1.

Check if the argument i has already been calculated and stored in our hash map memo. If so, return memo[i].

If we already have the value, we won’t recalculate it!

Otherwise, use the recurrence relation to calculate memo[i], and then return memo[i].

​

Bottom-Up

What is Bottom-Up dynamic programming?

• Bottom-up dynamic programming is also known as tabulation and is done iteratively (with loops).
• This is when the solution to a problem can be constructed from solutions to similar and smaller subproblems. Solving a smaller version of the problem can be easier and faster, thus if we break up the problem into smaller subproblems, solving them can lead us to the final solution easier and faster.

Bottom-Up approach

Let’s go back to the recurrence relation we found earlier:

Lets say minimumCost(i) represents the minimum cost to reach the ith step.

​

The base cases for this function will be

minimumCost(0) = minimumCost(1) = 0

since we are allowed to start on either step 0 or step 1.

​

For any other step i, we can write this as a recurrence:

minimumCost(i) = min(cost[i - 1] + minimumCost(i - 1),

cost[i - 2] + minimumCost(i - 2))

T(i) = T(i - 1) + T(i - 2)

​

​

​

Bottom-Up

What do we notice?

​

As you can see, we get the solution for the ith step by using solutions from earlier steps (just like in top-down dp!)

When does the sequence terminate?

• The base cases are given in the problem description - we are allowed to start at either step 0 or step 1, so minimumCost[0] and minimumCost[1] are both 0.

​

Bottom-Up Algorithm

• Define an array minimumCost, where minimumCost[i] represents the minimum cost of reaching the ith step. The array should be one element longer than costs (the “top” floor is one more than the cost of the steps to get there)
• Iterate over the array starting at the 2nd index. The problem statement says we are allowed to start at the 0th or 1st step, so we know the minimum cost to reach those steps is 0 (base case).
• For each step, apply the recurrence relation - minimumCost[i] = min(minimumCost[i - 1] + cost[i - 1], minimumCost[i - 2] + cost[i - 2]).
• As we populate minimumCost, it becomes possible to solve future subproblems. For example, before solving the 5th and 6th steps we are required to solve the 4th step.
• At the end, return the final element of minimumCost.
• We’re treating this "step" as the top floor that we need to reach.

Bottom-Up Code

class Solution {

public int minCostClimbingStairs(int[] cost) {

// The array's length should be 1 longer than the length of cost

// This is because we can treat the "top floor" as a step to reach

int minimumCost[] = new int[cost.length + 1];

// Start iteration from step 2, since the minimum cost of reaching

// step 0 and step 1 is 0

for (int i = 2; i < minimumCost.length; i++) {

int takeOneStep = minimumCost[i - 1] + cost[i - 1];

int takeTwoSteps = minimumCost[i - 2] + cost[i - 2];

minimumCost[i] = Math.min(takeOneStep, takeTwoSteps);

}

// The final element in minimumCost refers to the top floor

return minimumCost[minimumCost.length - 1];

}

}

​

Define an array minimumCost, where minimumCost[i] represents the minimum cost of reaching the ith step. The array should be one element longer than costs (the “top” floor is one more than the cost of the steps to get there)

Iterate over the array starting at the 2nd index, as we know the minimum cost to reach step 0 and 1 is 0

For each step, apply the recurrence relation - minimumCost[i] = min(minimumCost[i - 1] + cost[i - 1], minimumCost[i - 2] + cost[i - 2]).

At the end, return the final element of minimumCost. Remember, we are treating this "step" as the top floor that we need to reach.

Difference between bottom-up and top-down

If you’ll notice, they’re quite similar! It depends how your brain works and what makes more sense to you.

• If you like writing the recursive code first and then converting redundant calls to save space, top-down is probably your favorite!
• If you like deriving the recurrence relation directly from the problem and directly coding a DP solution, bottom-up is probably your favorite!

Both are equally good ways of solving a DP problem.

Ed: Coin Change

Coin Change

Coin Change Recurrence Intuition

Let’s look at an example:

​

coins = [1, 2, 3]

amount = 6

​

For a recurrence, we’re going to take the BOTTOM-UP approach in order to solve this: i.e. breaking our larger problem into smaller subproblems!

​

i.e. what’s the min amount of coins for amount 5? What about amount 4? Or 3?

​

Recurrence cont.

Let’s define these “subproblem” answers using F(i), where F(i) is the min number of coins for amount i, where i is between 0 and the amount given.

​

We have an example here:

Coin Change Cont.

What pattern do we notice?

• In order to figure out the optimal value for F(i), we have to check values of F(i - c_j), where c_j is the value of the coin.
• Think of this as using the coin, and finding the min coins GIVEN that we picked coin j!

Coin Change Cont.

Let’s put this pattern into a recurrence:

• F(i) = min_{j in 0…n-1}F(i - c_j) + 1

​

• In words, we’re finding the MINIMUM given that we selected the coin we’re on!
• Remember, this is how we would solve this recursively.

Coin Change Cont.

Given our recurrence:

• F(i) = min_{j in 0…n-1}F(i - c_j) + 1

​

• How would we write our top-down/bottom-up code?
• Top-Down: Write recursive code, use a hashmap/array to STORE calls that might be used more than once!
• Bottom-Up: Start from the base cases, building up the subproblems smallest to largest until you’ve solved the complete problem!

​

• The solutions for both approaches are on the Ed :) Have fun solving!