Dynamic Programming

Question 1

Rod cutting
You have a steel rod of length n. For a cut of length i in [1, n], you get Pi euros. The goal is to find cuts that maximize the total revenue

Answer 1

Subproblems: rob of length k < n to cut optimally
Rn = max(Pk + Rn-k) for k in [1,n]

Can be solved with DAG

Θ(n^2) time complexity

Question 2

(Facebook) House robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Return the maximum amount of money you can rob tonight without alerting the police.

Answer 2

Use DAG approach.

Two edges one from i to i+2 and one from i to i+3

Θ(n) time complexity

Question 3

011SS

How many ways are there to make a N-bit number in which there are no consecutive zeros?

For example, N = 3 answer is 5: 101, 010, 111, 110, 011

Answer 3

• Subproblem:
  Shorter binary strings
• Recurrence:
  M(0) = 1 (there is just one valid binary string with length 1
  M(1) = 2
  M(N) = M(N-1) + M(N-2)

Θ(n) time complexity

Question 4

Minimum Cost Path

Given a Matrix M (nxm) with integers, the goal is to compute the path of mincostr from top left corner to bottom right corner by moving only down or right.

Answer 4

Sub problems: min path from top left corner to any cell(i, j) in M

Comine sub problems: to reach the cell (i, j) check if it is better to come from (i-1, j) or (i, j-1)

Recurrence: W[i, j] = M[i, j] +
* 0 if i=j=1
* W[i, j-1] if i = 1 and j > 1 (first row)
* W[i-1, j] if i > 1 and j = 1 (first column)
* min(W[i-1, j], W[i, j-1]) otherwise

Θ(|M|) time complexity

Question 5

Longest Common Subsequence (LCS)
Given S1 of length n and S2 of ength m, find LCS(S1, S2)

Answer 5

Subproblems: compute LCS for prefixes of S1 and S2, LCS(i, j) = LCS(S1[1, i], S2[1, j])

Combine: given c1 = S1[i] and c2 = S2[i]
1. case 1, c1 == c2, LCS(i, j) = LCS(i-1, j-1) + 1
2. case 2, c1 != c2, LCS(i, j) = max{LCS(i, j-1), LCS(i-1, j)}

Recurrence: LCS(i, j) =
* 0 if i == 0 or j == 0
* 1 + LCS(i-1, j-1) if S1[i] == S2[j]
* max{LCS(i, j-1), LCS(i-1, j)} otherwise

Reconstruct the LCS with a bottom-up approach by taking the letters on which we move in the diagonal

Θ(n * m) time complexity

Question 6

0/1 knapsack problem

We have n items and a capacity C. Each item i has value vi and weight wi. Select a subset of items with total weight <= C that maximizes the overall value

Answer 6

Subproblems: select for any capacity <= C among any prefix of the items.
K(i, j) = optimal overall value for first i items and capacity j

Combine: K(i, j) =
* K(i - 1, j - wi) + vi if you select item i
* K(i - 1, j) if you don’t select item i

Recurrence: K(i, j) =
* 0 if i == 0
* max{ K(i - 1, j - wi) + vi, K(i - 1, j) }

Use a top-down approach to tell which items you take. Start from the last entry and if you are not going above then it means you selected that item

Θ(n * C) time complexity

Question 7

Fractional Knapsack problem
You can select a fraction f of item i. Cost is wi * f and revenue is vi * f

Answer 7

Optimal solution with Greedy strategy in Θ(nlogn) time. The optimal greedy solution also gives us an approximation of the 0/1 problem

Select items by largest vi/wi ratio (value per unit of weight). Then take a fraction of the last item

Θ(nlogn) time complexity

Question 8

Subset Sum Problem

Given a set S of n integers and a target value v. Is there any subset of S with sum v?

Answer 8

Recurrence: M[i, j] =
* true if i = j = 0
* false if i = 0 and j >= 1
* M[i-1, j] or M[1-1, j-S[i]) otherwise

Θ(n * v) time complexity

Question 9

Coin Change
Given a set of possible values for coins, count the number of ways we can make the change K using values we have

Answer 9

Recurrence: M[i, j] =
use ci -> M[i, j-ci] + do not use ci -> M[i-1, j]

Θ(n * k) time complexity

Question 10

Longest Increasing Subsequence (LIS)
Given a sequence S of n elements, find the LIS of S

Answer 10

Solution in Θ(n^2) time
DAG approach: S[i] is connected to S[j], which means (i,j) is an edge, if i < j and S[i] < S[j]

Solution in Θ(nlogn) time
* compute predecessor of current value
* keep in a BBST only the dominating positions: find successor y and remove it if LIS[y] <= LIS[current]

Another nlogn solution: https://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming

Question 11

Longest Bitonic Subsequence (LBS)
A subsequence that increases and then decreases

Answer 11

1. Find LIS
2. Find LDS
3. LBS[i] = LIS[i] + LDS[i] - 1
4. Take the largest LBS value

Θ(nlogn) time complexity

Question 12

Largest Independent Set on trees

Answer 12

Subproblems: LIST(u) = #nodes in the independent set of the subtree rooted at u

Combine: LIST(u) =
* 1 if u is a leaf
* max{ 1+sumForEachGranChild(LIST(granChild)), sumForEachChild(LIST(child)) }

Θ(n) time complexity

Question 13

Edit Distance

Find the minimum number of operations to transform S1 into S2.
Edit operations:
* Insert a symbol at a given position
* Delete a symbol at a given position
* Replace a symbol at a given position

Answer 13

Sub problems: Edit Distance of prefixes. ED(i, j) = Edit Distance of S1[1 … i] and S2[1 … j]

Combine: ED(i, j) =
* i if j == 0
* j if i == 0
* ED(i-1, j-1) if S[i] == S[j]
* 1 + min {
* ED(i, j-1), //Insert S[j] at pos i
* ED(i-1, j), //Delete at pos i
* ED(i-1, j-1), //Replace

More here: https://leetcode.com/problems/edit-distance/discuss/1217663/Edit-Distance-CPP-Recursive-Memoization-Top-Down-all-approaches-with-explanation

Θ(n * m) time complexity