Dynamic Progamming 1: FIB, LIS, and LCS

Question 1

What is the recipe for solving dynamic programming problems?

Answer 1

1) Define the subproblem F[i] in words. Always start by trying an identical problem on a prefix (the first i-1 items) of the input.

2) State the recursive relation, i.e. define F[i] as a recursive function of F[1] … F[i-1].

Refine the above definitions to arrive at the solution. Often this means adding a constraint to step one. A common constraint is that we require a_i (the last element of the prefix) is included in the solution to F[i].

If we add that constraint, we cannot just return the last element of our table, but instead need to take a min or max over the table.

Question 2

What does it mean that we don’t use recursion in our solutions to DP problems?

Answer 2

We use recursion in the sense that we define a recursive relation, but we do not use recursive function calls in the algorithm itself.

Question 3

What is memoization?

Answer 3

Memoization is when you use a recursive solution, but track the results of subproblems (e.g., in a hash table) to avoid recomputing them. We will NOT use this in our course because:

1) The recursive calls make it slower
2) The recursive calls also make them harder to analyze (re: time complexity)