Dynamic Programming

Notes

It's an extension of the Divide and Conquer paradigm
It works by recursively breaking down a problem into two or more sub-problems, until these become simple enough to be solved directly. The combination of the solutions for the sub-problems is a solution for the original problem.
There are two key attributes that divide and conquer must have in order for dynamic programming to be applicable:
- Optimal substructure - optimal solution can be constructed from optimal solutions of its sub-problems
- Overlapping sub-problems - problem can be broken down into sub-problems which are reused several times, or a recursive algorithm for the problem solves the same sub-problem over and over rather than always generating new sub-problems

There are two main techniques of caching and reusing previously computed results:

Memoization (top-down cache filling): usually done recursively

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)
        mem[n] = result
    return mem[n]
}

Tabulation (bottom-up cache filling): usually done iteratively

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

How do I recognise a Dynamic Programming problem?

Recognize a dynamic programming problem. This is often the most difficult step and it has to do with recognizing that there exists a recursive relation. Can your problem result be expressed as a function of results of the smaller problems that look the same?
Determine the number of changing parameters. Express your problem in terms of the function parameters and see how many of those parameters are changing. Typically you will have one or two, but technically this could be any number. Typical examples for one parameter problems are fibonacci or a coin change problem, for two parameter is edit distance.
Clearly express the recursive relation. Once you figure out that the recursive relation exists and you specify the problems in terms of parameters, this should come as a natural step. How do problems relate to each other. That is, assuming that you have computed the subproblems, how would you compute the main problem.
What are your base cases? When you break down sub-problems into smaller sub-problems and you break down those even further, what is the point where you cannot break it anymore? Do all these subproblems end up depending on the same small subproblem or several of them?
Decide if you want to implement it iteratively or recursively and be comfortable with both. Know the trade-offs between one or the other, such as recursive stack overflow, sparsity of computation, think if this is a repeated work or something that you always do online, etc.
Add memoization. If you’re implementing it recursively, add memoization. If you’re doing it iteratively, this will come for free. Adding memoization should be super mechanical. Just see if you have memoized the state at the beginning of your function and add it to memoization before each return statement. Memoization value should almost always be the result of your function.
Time complexity = (# of possible states * work done per each state). This should also be relatively mechanical. Count the number of states that you can have. This will be linear if you have a single parameter, quadratic if you have two and so on. Think about the work done per each state - that is the work that you have to do assuming that you’ve computed all of the subproblems.

Problems solved using Dynamic Programming

Balanced Partition - given a set of n integers between 0 and K, partition these integers into two sets so that |sum(S1) - sum(s2)| is minimal
Climbing Stairs - given a staircase with n steps to the top, and you can climb x or y steps, in how many disinct ways can you reach the top of the staircase?
Coin Change - given an infinite supply of coins with different values and a target price, in how many distinct ways can we make the change?
Fibonacci Sequence - what is the n-th number in the Fibonacci sequence?
House Robber
Knapsack - given a set of items, each with a weight and a value, what is the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible?
Longest Common Subsequence - given two strings, what is the longest subsequence (=non necessarily contiguous) for which letters from the two strings appear in the same order?
Maximum Subarray Sum - given an array of integers, which contiguous subarray has the largest sum?
Minimum Edit Distance (or Levenshtein Distance) - what is the minimum number of single-character edits (insertions, deletions, or subsitutions) required to change one word into another?