Dynamic Programming
Last updated
Was this helpful?
Last updated
Was this helpful?
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
Tabulation (bottom-up cache filling): usually done iteratively
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.
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.
Problem List:
Problem List:
Problem List:
Problem List:
Problem List:
- given a set of n integers between 0 and K, partition these integers into two sets so that |sum(S1) - sum(s2)| is minimal
- 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?
- given an infinite supply of coins with different values and a target price, in how many distinct ways can we make the change?
- what is the n-th number in the Fibonacci sequence?
- 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?
- given two strings, what is the longest subsequence (=non necessarily contiguous) for which letters from the two strings appear in the same order?
- given an array of integers, which contiguous subarray has the largest sum?
Minimum Edit Distance (or ) - what is the minimum number of single-character edits (insertions, deletions, or subsitutions) required to change one word into another?
- LeetCode
- Quentin Santos
- Oleksii Trekhleb
- programming.guide
- Nikola Otasevic
- Jesse Farmer
- Quora
Introduction To Algorithms, Chapter 15: Dynamic Programming (, )
- MIT
- Udemy
- Educative
- Udemy
- Udemy
- Michael A. Trick
- Brian Dean
- Tushar Roy
- William Fiset
- NPTEL
- Stanford CS221
- Coding Patterns