11a. DP Review

1. Make own review sheet
2. Practice problems with LLM
3. Come up with own practice problems

1: Given $n$ rods of varying length, see if a combined rod of length $S$ is possible (can reuse rods)

knapsack

A. Precise subproblems

Can we form some length $i$ using the available rod lengths?

B. Base Case and Recurrence

1. if some length $i$ is equal to a single rod length, then true
2. length 0 can be made

Recurrence

$T(n)=OR(n-l_k)$ for any length $k$ in the input set

Show solution to original problem can be found by solving problems

Since the algorithm solves for any length $i$, we can find length $S$.

order for subproblems

linear starting from length $1$ to length $S$ since we have to use subproblems we already solved to get a $T(i)$.

running time

$O(S)$ since we run for each state, then $O(n)$ for each given rod length. Therefore, $O(Sn)$.

2. Given three strings X, Y, and Z, return true if Z is X and Y interweaved (X and Y are subsequences in Z)

First iteration: check if first element in Z is the first element of X or Y

Subproblems Definition

Is an element $D(i)$ in X or Y and has X(i - 1) or Y(i - 1) true?

Base Case and Recurrence

An element $dp[i][j]$ is true if X[i] == Z[i + j]and $X[i-1]$ is true, or $Y[j-1]$ and $Y[i]=Z[i+j$]

Show Solu obtained from Subproblems

We can check if a string Z is a combination of X and Y by incrementally checking subsequences where $Z=i+j$

Determine order received subproblems

Start from first element to last

running time

$O(mn)$ because we go $O(mn)$ through 2d matrix

Min sum grid traversal (top-left to bottom-right)

Precise Subproblem

What is the minimum sum moving from $(0,0)$ to $(n-1,n-1)$?

Base Case + Recurrence

Base Case is the integer at $(0,0)$ We set $dp[0][j]$ to 0 and $dp[0][i]$ to 0

Recurrence $dp[i][j]=min(dp[i-1][j],dp[i][j-1])+M[i-1][j-1]$

Solu can be obtained from subproblems

Since we can get min sum at an arbitrary $i,j$, we can get min sum for $(n-1,n-1)$

order

solve $dp[1][1]$ first which corresponds to $matrix[0][0]$ and go for each elem in row for each col

running time

$O(mn)$ for looping through matrix

6.3 Yuckdonald Max Profit

Subproblems:

At a location $i$, set $dp[i]=max(dp[i-k]+p_i,dp[i-1])$

Either take and add to profit - k or don’t take and maintain last one What is the max profit if we either open a restaurant at a location and the location k miles away, or don’t open one and take the last one?

Recurrence

Base case at 0 is 0