(W6) Dynamic Programming

Question 1

What is the big idea of Dynamic Programming?

Answer 1

Memo-ize the smaller problems, so we don’t solve the same problem more than once

(think fib numbers, if we don’t memoize we are gonna repeat calculations for ages)

Question 2

Bottom up approach vs top down approach

Pros and cons of each

Answer 2

Bottom up avoids recursion (lower space complexity), but often has to calculate each subproblem from {0, n}

Top down often can just calculate the required problems - but has to use recursion (so increased stack space)

Question 3

Overlapping subproblems vs optimal substructure?

Answer 3

Overlapping subproblems - problems that will be solved multiple times

Optimal substructure - when a solution can be found from the values of it’s overlapping subproblems

Question 4

How to find the longest increasing subsequence of an array (using DP)

Answer 4

Overlapping Subproblems: DP[i] = the length of the longest increasing subsequence that ends at i

Logically: an increasing subsequences at x cannot include a value higher than x in the previous part of the array. so you could select any value - but we want the longest increasing subsequence, so pick the maximum value in the preceding array

Value of DP[i] is the maximum number between 0 < and i. DP[i] = DP[of this max number] + 1

Question 5

How to find the subarray (continuous) of array a with the maximum sum

Answer 5

DP[i] = { sum of all elements in a[1..i] }

max sum will be the max value of DP[j] - DP[i] - where 0 <= i <= j <= n, so try each combination

Question 6

Recurrence of the Coin Change problem?

Answer 6

Trying to make $v

1. 0 if v = 0
2. inf if v > 0 and v < c[i] for all i
   - this means that all coins are larger than $v (so not possible)
3. min(1 + mincoins[v - c[i])
   (where i is the index of the coins provided)
   (cost of each coin must be <= v)

Question 7

Solve the ‘cross the road and pickup the rock or stay on your side’ problem with dynamic programming

Answer 7

Keep two DP arrays
DPleft[i] = {max amount if we start from pavement at i}
DPright[i] = {max amount if we start from pavement at i}

Approach, work your way down

DPleft:
- left[n] if i = n (so base case)
otherwise, max of left[i] + DPleft[i+1] OR switch sides DPright[i+1]

Same for DPright

Question 8

Solve the ‘you can only take the first or last coin problem, what is the total value of coins you can take’ problem with Dynamic Programming

Answer 8

DP[i , j ] = {The maximum score that we can obtain playing first from the subarray a [i.. j ]}

Note that if I take the first coin, then my friend will take the max value from [1, n] coins

So I will be able to get whats left over - sum(1,n) - dp(1,n)

Question 9

What is the recurrence relation with 0/1 Knapsack problem?

Answer 9

Max[i,c] = {max value we can fit in a capacity of c using items 1 to i}

Two options:
Either weight of item i is > capacity, in which case, use i-1 items
Or pick the max between taking i-1 items, or taking current item + i-1 items and remaining space

max[i,c] = 0 if i = 0
max[i-1,c] if wi > c
max(max[i-1], c) OR value + max[i-1, c-weight)