Intro
Dynamic programming is tough, it really is. But unfortunately, it’s one of those topics that keeps popping up in interviews, so there is no other option than mastering it. In this post, I tried to explain some of the DP approaches for my future interviews. I hope it will be beneficial for anyone who’s reading. For more interview patterns, check out my LeetCode Cheatsheet for Coding Interviews and Graph questions cheatsheet. Also, if you’re using Python for interviews—or thinking about it—my Python for Interviews Cheatsheet might be helpful too. Enough talk—let’s dive in.
Minimum (Maximum) Path to Reach a Target
Overview
This pattern involves finding the minimum or maximum cost/path to reach a target. Problems in this category often require you to make decisions at each step that contribute to an overall optimal solution.
Key Characteristics
- Optimization Objective: Minimize or maximize a certain value.
- Subproblem Overlapping: The problem can be broken down into smaller, overlapping subproblems.
- State Definition: The DP state typically represents the minimum or maximum value to reach a certain point.
Example Problem: 322. Coin Change
Problem Description
Given an integer array coins
representing coins of different denominations and an integer amount
, return the fewest number of coins needed to make up that amount. If it’s impossible, return -1
.
Example:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Solution Explanation
We need to find the minimum number of coins that sum up to the target amount. This is a classic example of the minimum path to reach a target.
Steps
-
Define the DP Array:
dp[i]
represents the minimum number of coins needed to make up amounti
. -
Initialize the DP Array: Set
dp[0] = 0
since zero coins are needed to make up amount zero. Initialize the rest with a value greater than the maximum possible (e.g.,amount + 1
). -
Iterate and Update: For each amount from
1
toamount
, iterate through the coins and updatedp[i]
accordingly. -
Return the Result: If
dp[amount]
is greater thanamount
, return-1
, indicating it’s impossible to make up the amount. Otherwise, returndp[amount]
.
Code
Complexity Analysis
- Time Complexity: O(amount * n), where ‘n’ is the number of coin denominations.
- Space Complexity: O(amount), for the DP array.
Distinct Ways
Overview
This pattern deals with counting the number of distinct ways to achieve a certain goal. It’s common in problems where you need to find the number of different combinations or sequences that satisfy certain conditions.
Key Characteristics
- Counting Solutions: Focused on counting the number of ways rather than finding the way itself.
- Recursive Substructure: The total number of ways can be expressed in terms of the number of ways to reach smaller subproblems.
- State Definition: The DP state usually represents the number of ways to reach a particular state or sum.
Example Problem: 494. Target Sum
Problem Description
Given an integer array nums
and an integer target
, you can add '+'
or '-'
before each number in nums
to form an expression. Return the number of different expressions that evaluate to target
.
Example:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Solution Explanation
We need to find the number of ways to assign '+'
or '-'
to each number such that the total sum equals the target.
Steps
-
Calculate the Total Sum: Compute the sum of all numbers in
nums
. -
Check Feasibility: If
(sum_nums + target)
is odd ortarget
is greater thansum_nums
, return0
. -
Transform the Problem: Convert it into a subset sum problem:
s = (sum_nums + target) // 2
-
Define the DP Array:
dp[i]
represents the number of ways to reach sumi
. -
Initialize the DP Array:
dp[0] = 1
, as there’s one way to reach sum0
(by choosing no elements). -
Iterate and Update: For each number in
nums
, update the DP array in reverse to avoid overwriting.
Code
Complexity Analysis
- Time Complexity: O(n * s), where ‘s’ is the subset sum.
- Space Complexity: O(s), for the DP array.
DP on Strings
Overview
This pattern involves solving problems related to string manipulation, such as finding subsequences, substrings, or matching patterns.
Key Characteristics
- Two-Dimensional DP: Often requires a 2D DP array since operations involve two strings or two indices.
- State Definition: The DP state typically represents the solution to a substring or subsequence ending at certain indices.
- Common Problems: Longest Common Subsequence, Edit Distance, String Matching.
Example Problem: 1143. Longest Common Subsequence
Problem Description
Given two strings text1
and text2
, return the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguous.
Example:
Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.
Solution Explanation
We need to find the length of the longest sequence that appears in both strings.
Steps
-
Define the DP Array:
dp[i][j]
represents the length of the longest common subsequence betweentext1[0...i-1]
andtext2[0...j-1]
. -
Initialize the DP Array:
dp[0][j] = 0
anddp[i][0] = 0
because an empty string has a common subsequence length of0
. -
Iterate and Update:
- If
text1[i-1] == text2[j-1]
, thendp[i][j] = dp[i-1][j-1] + 1
. - Else,
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
.
- If
-
Return the Result:
dp[m][n]
will have the length of the longest common subsequence.
Code
Complexity Analysis
- Time Complexity: O(m * n), where ‘m’ and ‘n’ are the lengths of the two strings.
- Space Complexity: O(m * n), for the DP array.
Decision Making
Overview
This pattern involves making decisions at each step to optimize a certain objective, often under certain constraints.
Key Characteristics
- Choice at Each Step: Decide whether to take an action or skip it.
- State Definition: The DP state includes parameters that represent decisions made so far.
- Common Problems: Stock trading, scheduling with penalties, or any scenario where decisions affect future outcomes.
Example Problem: 198. House Robber
Problem Description
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, and you cannot rob two adjacent houses because it will alert the police. Given an integer array nums
representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Solution Explanation
We need to maximize the profit by deciding whether to rob each house or skip it, while ensuring we don’t rob two adjacent houses.
Steps
-
Define the DP Array:
- Let
dp[i]
be the maximum profit achievable by robbing up to thei-th
house.
- Let
-
Initialize Base Cases:
- If there are no houses (
nums
is empty), the maximum profit is0
. - If there is only one house, the maximum profit is
nums[0]
.
- If there are no houses (
-
Fill the DP Array:
- For each house from the second house onward:
dp[i]
will be the maximum of:- Robbing the
i-th
house and adding its value todp[i-2]
(skip one house). - Skipping the
i-th
house and taking the value fromdp[i-1]
.
- Robbing the
- For each house from the second house onward:
-
Return the Result: The last element in
dp
represents the maximum profit achievable.
Code
Optimized Code (Space Optimization)
Since we only need the last two states at each step, we can reduce space complexity to O(1)
:
Complexity Analysis
- Time Complexity: O(n), where ‘n’ is the number of houses.
- Space Complexity: O(1), due to constant space usage in the optimized solution.
Example Problem: 714. Best Time to Buy and Sell Stock with Transaction Fee
Problem Description
You are given an array prices
where prices[i]
is the price of a stock on day i
and an integer fee
representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. Return the maximum profit you can achieve.
Example:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Solution Explanation
We need to maximize profit by deciding whether to buy, sell, or do nothing on each day.
Steps
-
Define the DP States:
hold
: Maximum profit when holding a stock.cash
: Maximum profit when not holding a stock.
-
Initialize the States:
hold = -prices[0]
(We buy the first stock).cash = 0
(No profit initially).
-
Iterate and Update:
- For each price in
prices[1:]
:- Update
cash
as the maximum of itself andhold + price - fee
(sell stock). - Update
hold
as the maximum of itself andcash - price
(buy stock).
- Update
- For each price in
-
Return the Result: The
cash
variable will have the maximum profit.
Code
Complexity Analysis
- Time Complexity: O(n), where ‘n’ is the number of days.
- Space Complexity: O(1), as we use constant extra space.