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.

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).
- Problem List: DP (Max - Min)
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).
- Problem List: DP (distinct ways)
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.
- Problem List: DP (merging intervals)
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
- Problem List: DP on strings
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.
- Problem List: DP (decision making)

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?

Resources

Articles

DP IS EASY! 5 Steps to Think Through DP Questions - LeetCode
Dynamic Programming is not Black Magic - Quentin Santos
Dynamic Programming vs Divide-and-Conquer - Oleksii Trekhleb
Dynamic programming vs memoization vs tabulation - programming.guide
Dynamic Programming – 7 Steps to Solve any DP Interview Problem - Nikola Otasevic
Introduction to Dynamic Programming - Jesse Farmer
What are the top 10 most popular dynamic programming problems among interviewers? - Quora

Books

Algorithms, Chapter 6: Dynamic Programming
Introduction To Algorithms, Chapter 15: Dynamic Programming (lecture, notes)

Courses

Dynamic Programming - MIT
Dynamic Programming - I - Udemy
Grokking Dynamic Programming Patterns for Coding Interviews - Educative
Intro To Dynamic Programming - Coding Interview Preparation - Udemy
Master the art of Dynamic Programming - Udemy

LeetCode Problems

Last updated 4 days ago

Was this helpful?