A couple of quick notes before summarizing some common Dynamic Programming Patterns, how to recognize them and how their recurrence relations work:
- Do not memorize patterns to get good at DP. Have them as reference points in your head in case your stuck.
- Always think of DP as an afterthought after thinking how a problem can be solved recursively (i.e. think of the "Optimal Substructure" property first and then use DP to reduce redundant work from the "Overlapping Subproblems")
- The intuition for DP comes from the Top-Down appraoch of thinking of it (i.e. the "Optimal Substructure) - Bottom Up approaches are optimizations. You should explain your solution with Top-Down logic, even if you want to eventually optimize with Bottom-Up.
When explaining DP solutions:
- Use appropriate terminology - refering to states, transitions, recurrence relations etc. will make it a lot easier for interviewers to follow your reasoning.
- Clearly state your recurrence relation / logic before coding.
- Demonstrate that you understand how DP has optimized your solution by contrasting its runtime with the Brute Force solution, where appropriate.
- Demonstrate that you code works with Test Cases (especially important to demonstrate that there are Overlapping Subproblems).
e.g. Knapsack Problem
Maximization problems often provide a recurrence relation of the form:
dp[i] = max(dp[transitions to all states before i]....)
in the case of Knapsack, the state is given by two variables instead: i, the index of the item we're currently considering and W, the current capacity we have left and we get a recurrence relation of the form:
KS[i][W] = max(val[i] + KS[i-1][W-weight[i]], KS[i-1][W])
- we have 2 state transitions: 1 where we put the item in our bag and need to increment by its value, and 1 where we don't put the item in our bag.
I like to think of the above as a graph where an edge from A to B says that A needs to be solved before B and the operations on each edge dictate how the value changes to solve the larger problem:
In this case we take the MAX of all incoming edges
When the problem dictates that you should find the maximal value, consider finding a relation of the above form. Normally the difficulty lies in figuring out what variables will give the state of the problem.
Classics
- Knapsack
- Rod Cutting Problem
- Longest Increasing Subsequence (Leetcode) - DP is not the optimal solution here
Leetcode
Minimzation is pretty much the same as the above but with min instead:
dp[i] = min(dp[transitions to all states before i]....)
For something like the coin change problem where n represents the value which I want to make with the minimum amount of coins:
change[n] = min(change[n-val[coin]] for all coins.... + 1)
In this case we have at most C transitions where C is the amount of coins in my set, e.g. if my coin set was [1, 5, 10, 25] the above relation would be
change[n] = min(change[n-1] + 1, change[n-5] + 1, change[n-10] + 1, change[n-25] + 1)
or more concisely
change[n] = min(change[n-1], change[n-5], change[n-10], change[n-25]) + 1
As a graph it becoems:
In this case we take the MIN of all incoming edges
Classic:
Leetcode:
- Dungeon Game
- 2 Keys Keyboard
- Triangle
- Minimum Falling Path Sum
- Minimum Cost For Tickets
- Minimum Number of Refueling Stops
For counting we would use a sum of all subproblems instead:
dp[i] = sum(dp[transitions to all states before i]...)
For example, the Knight Dialer problem we covered in our second Dynamic Programming session has a recurrence relation where n is the number of digits and i is the digit you're currently on:
knight[n][i] = sum(knight[n-1][j] for all j that you can reach from i)
e.g. if i was 1 it would be
knight[n][1] = sum(knight[n-1][6], knight[n-1][8]
Typically we don't increment on subproblems here because the summation already increments our value up the recursion but this is not a law.
In this case we take the MIN of all incoming edges
Classic:
Leetcode:
- Knight Probability in Chess Board
- Knight Dialer
- Partition Equal Subset Sum
- Soup Servings
- Unique Paths II
- Number of Ways to Stay in the Same Place After Some Steps
- Count Vowels Permutation
For this, I'm going to recommend going over some classic problems as they tend to be tricky and a variation of these.