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 solution can be constructed from optimal solutions of its 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:

(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.

Patterns

Minimum (Maximum) Path to React a Target
- Given a target find minimum (maximum) cost / path / sum to reach the target.
- Approach: Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.
- Generate optimal solutions for all values in the target and return the value for the target (Top-down, Bottom-up).
Distinct Ways
- Given a target find a number of distinct ways to reach the target.
- Approach: Sum all possible ways to reach the current state.
- Generate sum for all values in the target and return the value for the target (Top-down, Bottom-up).
Merging Intervals
- Given a set of numbers find an optimal solution for a problem considering the current number and the best you can get from the left and right sides.
- Approach: Find all optimal solutions for every interval and return the best possible answer.
- Get the best from the left and right sides and add a solution for the current position.
DP on Strings
- General problem statement for this pattern can vary but most of the time you are given two strings where lengths of those strings are not big
- Approach: Most of the problems on this pattern requires a solution that can be accepted in O(n^2) complexity.
- If you are given one string s the approach may little vary
Decision Making
- The general problem statement for this pattern is forgiven situation decide whether to use or not to use the current state. So, the problem requires you to make a decision at a current state.
- Approach: If you decide to choose the current value use the previous result where the value was ignored; vice-versa, if you decide to ignore the current value use previous result where value was used.

Dynamic Programming

Notes

How do I recognise a Dynamic Programming problem?

Patterns

Problems solved using Dynamic Programming

Resources

Articles

Books

Courses

LeetCode Problems

Websites

YouTube playlists

YouTube videos

Notes

How do I recognise a Dynamic Programming problem?

Patterns

Problems solved using Dynamic Programming

Resources

Articles

Books

Courses

LeetCode Problems

Websites

YouTube playlists

YouTube videos