Course: AlgoMonster — Dynamic Programming Patterns for Coding Interviews Core idea: You don't need to memorize hundreds of DP problems — master a small set of recurring patterns, and most problems become variations of the same idea.
- What is Dynamic Programming?
- Pattern 1: Constant Transition (Fixed Number of Previous States)
- Memoization vs. Tabulation
- Pattern 2: Grid DP (2D Table, One Sequence Given as Grid)
- Pattern 3: Two Sequences DP
- Pattern 4: Interval DP
- Pattern 5: Non-Constant Transition (Variable Dependencies)
- Pattern 6: Knapsack-Like Problems
- Master Pattern-Recognition Cheat Sheet
- All Solved Problems — Quick Index
Dynamic Programming (DP) = breaking a complex problem into simple, reusable subproblems, solving each subproblem only once, and reusing the results instead of recomputing them.
The single most important skill: recognize which pattern a new problem belongs to. Once recognized, the formula/transition almost writes itself.
The 6 patterns covered in this course:
| # | Pattern | Signal |
|---|---|---|
| 1 | Constant Transition | Answer depends on a fixed small number of previous states (e.g., last 2) |
| 2 | Grid DP | 2D grid, movement restricted (e.g., only right/down) |
| 3 | Two Sequences DP | Comparing two strings/arrays |
| 4 | Interval DP | One sequence; need optimal answer over a sub-interval [i, j] |
| 5 | Non-Constant Transition | Answer depends on all (or a variable number of) previous states |
| 6 | Knapsack-Like | Need to check if a target sum is reachable using array elements |
Statement: A staircase has n steps. From any step you can climb 1 step or jump 2 steps. Count the number of distinct ways to reach the top.
Key Insight:
- To reach step
n, you can only have come from stepn-1(by 1 step) or stepn-2(by a 2-jump). - Every path to step
n-1orn-2can simply be extended — no new paths are "created," they're just extended.
ways(n) = ways(n-1) + ways(n-2)
Base cases:
ways(1) = 1
ways(2) = 2
def ways(n):
if n == 1: return 1
if n == 2: return 2
return ways(n-1) + ways(n-2)- Problem:
ways(3)gets recomputed many times insideways(5),ways(6), etc. - The recursion tree explodes: Time Complexity = O(2^n).
- Even
n = 30→ ~1 billion redundant calls.
Memoization = recursion with memory. Store each computed result in a hashmap (key = step number, value = number of ways). Before recomputing, check the cache first.
def ways(n, memo={}):
if n in memo:
return memo[n]
if n == 1: return 1
if n == 2: return 2
memo[n] = ways(n-1, memo) + ways(n-2, memo)
return memo[n]- Time Complexity: O(n) — each step computed exactly once.
- Space Complexity: O(n) — hashmap + recursion call stack.
Tabulation = fill a table iteratively from base cases up to the final answer. No recursion, no call stack.
def ways(n):
if n == 1: return 1
if n == 2: return 2
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]- Time: O(n), Space: O(n).
Since dp[i] only ever needs the last 2 values, we don't need the whole array — just 2 variables.
def ways(n):
if n == 1: return 1
if n == 2: return 2
a, b = 1, 2
for i in range(3, n + 1):
a, b = b, a + b
return b- Time: O(n), Space: O(1).
| Memoization (Top-Down) | Tabulation (Bottom-Up) | |
|---|---|---|
| Direction | Top-down (recursive) | Bottom-up (iterative) |
| Memory | Cache + call stack | Just an array |
| Best for | Order of subproblems unclear (e.g., partition problems — splitting strings/arrays) | Order is clear/sequential |
| Risk | Stack overflow for large n |
None (no recursion) |
| Complexity analysis | Sometimes harder to see | Usually easier to see (visible loop cost) |
Rule of thumb: If you can clearly see the order to fill values one-by-one → use Tabulation. If the order is unclear or the problem involves partitioning → Memoization is more convenient, since recursion naturally explores whatever sub-problems are needed.
Each term = sum of the previous 3 terms (instead of 2).
T(0) = 0, T(1) = 1, T(2) = 1
T(n) = T(n-1) + T(n-2) + T(n-3)
Optimized O(1) space solution (3 rolling variables):
def tribonacci(n):
if n == 0: return 0
if n in (1, 2): return 1
t0, t1, t2 = 0, 1, 1
for i in range(3, n + 1):
t0, t1, t2 = t1, t2, t0 + t1 + t2
return t2- Time: O(n), Space: O(1).
Statement: Given a cost array (price to land on each stair). Start from stair 0 or 1. Move 1 or 2 stairs at a time. Find the minimum cost to reach the top (the floor beyond the last stair — free to land on).
minCost(n) = cost[n] + min(minCost(n-1), minCost(n-2))
Base cases:
minCost(0) = cost[0]
minCost(1) = cost[1]
Final answer = min(minCost(last), minCost(second-to-last))
O(1) space solution:
def minCostClimbingStairs(cost):
n = len(cost)
if n == 0: return 0
if n <= 2: return min(cost)
a, b = cost[0], cost[1]
for i in range(2, n):
a, b = b, cost[i] + min(a, b)
return min(a, b)- Time: O(n), Space: O(1).
Statement: Array of house values. Cannot rob two adjacent houses. Maximize total loot.
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Base cases:
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
O(1) space solution:
def rob(nums):
n = len(nums)
if n == 0: return 0
if n <= 2: return max(nums)
a, b = nums[0], max(nums[0], nums[1])
for i in range(2, n):
a, b = b, max(b, a + nums[i])
return b- Time: O(n), Space: O(1).
- State depends on a fixed number of previous states (e.g., always exactly 2 or 3).
- The transition formula is the same at every step.
- Memory can be optimized — no need to store the full array, just the last
kvalues.
(Summarized in section 2.6 above — repeated here as a standalone concept since it applies to ALL patterns, not just Pattern 1.)
- Memoization = top-down recursion + cache (hashmap).
- Tabulation = bottom-up iterative table-filling.
- Both typically achieve the same optimized time complexity — the choice is about code clarity, stack-safety, and how obvious the subproblem order is.
Statement: An m x n grid. Start top-left, reach bottom-right. Can move only right or down. Count unique paths.
Key Insight: A cell can only be reached from the cell above it or the cell to its left. So:
paths[i][j] = paths[i-1][j] + paths[i][j-1]
Base cases:
- First row: paths[0][j] = 1 for all j (only 1 way — keep moving right)
- First column: paths[i][0] = 1 for all i (only 1 way — keep moving down)
Full 2D Table Solution:
def uniquePaths(m, n):
paths = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
paths[i][j] = paths[i-1][j] + paths[i][j-1]
return paths[m-1][n-1]- Time: O(m·n), Space: O(m·n).
Space-Optimized (1 row only):
To compute the current row, you only need: (a) the row above (for the "up" value) and (b) the current row's already-updated left cell.
def uniquePaths(m, n):
row = [1] * n
for i in range(1, m):
for j in range(1, n):
row[j] = row[j] + row[j-1] # row[j] still holds "value from above"
return row[-1]- Time: O(m·n), Space: O(n) (or
O(min(m, n))if you store the shorter dimension).
Statement: Same as above, but grid cells contain 0 (free) or 1 (obstacle — cannot pass).
Key Insight: If a cell has an obstacle, dp for that cell = 0 (no paths through it at all).
Space-Optimized Solution:
def uniquePathsWithObstacles(grid):
if grid[0][0] == 1:
return 0
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = 1
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
dp[j] = 0
elif j > 0:
dp[j] += dp[j-1]
return dp[-1]- Time: O(m·n), Space: O(n).
- Two-dimensional space: a table, grid, or matrix.
- Movement is restricted (usually only right/down, sometimes other limited directions).
- Each cell's state depends only on specific neighboring cells (the ones you're allowed to arrive from).
- Clear base cases exist at the edges (first row/column) — fill these first.
Strategy: Build a table → fill the borders (base cases) → compute remaining cells using a formula derived from the movement rules.
Statement: Given two strings, find the length of their longest common subsequence (characters in the same relative order, but not necessarily contiguous — unlike a substring).
Subsequence vs. Substring: In "stone" → "ton" is a substring (consecutive), "toe" is a subsequence (order preserved, gaps allowed).
Why brute force fails: A string of length n has 2^n possible subsequences → for n=1000, computationally impossible.
Key Insight — Build a 2D table:
- Row index
i= position in string 1, Column indexj= position in string 2. dp[i][j]= length of LCS between the firsticharacters of string 1 and firstjcharacters of string 2.- Extra row/column of index
0represents the empty string (base case: LCS with empty string = 0).
If s1[i-1] == s2[j-1]: # characters match
dp[i][j] = dp[i-1][j-1] + 1 # diagonal + 1
Else: # characters differ
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # best of "skip from s1" or "skip from s2"
Base case: dp[0][j] = dp[i][0] = 0
Answer: dp[m][n] (bottom-right cell)
Full Table Solution:
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]- Time: O(m·n), Space: O(m·n).
Space-Optimized (2 rows only):
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev, curr = curr, prev
return prev[n]- Time: O(m·n), Space: O(n) (or
O(min(m,n))).
Statement: Given two strings, find the minimum number of operations (insert, delete, replace) to convert string 1 into string 2.
If chars match:
dp[i][j] = dp[i-1][j-1] # no operation needed
Else:
dp[i][j] = 1 + min(dp[i-1][j-1], # replace
dp[i-1][j], # delete
dp[i][j-1]) # insert
Base cases:
dp[i][0] = i (delete all i characters to match empty string)
dp[0][j] = j (insert all j characters)
Answer: dp[m][n]
Solution:
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
return dp[m][n]- Time: O(m·n), Space: O(m·n) (can also be optimized to
O(n)using 2 rows).
- Two sequences given (strings, arrays, lists) that need comparison.
- Task: find something in common, or count operations to transform one into the other.
- Build a 2D table: one sequence along rows, other along columns; base cases on the edges.
- Transition depends on comparing current elements — one formula if equal, another if not.
Related problems using this pattern: Longest Common Subsequence, Edit Distance, Shortest Common Supersequence.
Statement: Given one string, find the length of the longest subsequence that is a palindrome.
Key Insight:
- A palindrome = matching outer characters + a palindrome inside them.
- We don't need all
2^nsubsequences — instead work with intervals[i, j](only ~n²/2total intervals, vastly fewer). dp[i][j]= length of longest palindromic subsequence within the substring from indexitoj.
Base case: dp[i][i] = 1 (single character is always a palindrome)
If s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2 # both outer chars included
Else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1]) # drop left char OR drop right char
Answer: dp[0][n-1]
dp[i][j] depends on the smaller inner interval dp[i+1][j-1]. So: all length-1 intervals first (diagonal), then length-2, then length-3, etc.
Full Table Solution:
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]- Time: O(n²), Space: O(n²).
Space-Optimized (2 rows, filled bottom-to-top):
def longestPalindromeSubseq(s):
n = len(s)
prev = [0] * n
for i in range(n - 1, -1, -1):
curr = [0] * n
curr[i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
curr[j] = prev[j-1] + 2
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
return prev[n-1]- Time: O(n²), Space: O(n).
Statement: Count how many substrings of a given string are palindromes.
Approach (Recursive + Memoization variant of Interval DP):
from functools import lru_cache
def countSubstrings(s):
n = len(s)
count = 0
@lru_cache(maxsize=None)
def isPalindrome(i, j):
if i >= j:
return True
if s[i] != s[j]:
return False
return isPalindrome(i + 1, j - 1)
for i in range(n):
for j in range(i, n):
if isPalindrome(i, j):
count += 1
return count- Time: O(n²) (checking all substrings, each check is O(1) amortized thanks to memoization).
- Space: O(n²) (memoization cache stores results for all intervals).
Note: Interval DP problems can be solved either via an explicit bottom-up table (by interval length) or top-down recursion + memoization — both are valid; recursion is sometimes more intuitive for interval problems.
- One sequence (not two).
- Need the optimal result over a sub-interval
[i, j]of that sequence. - Result for a larger interval depends on results for smaller nested intervals (left/right boundary shrinks).
- Table must be filled by interval length (short → long), not row-by-row.
- Base cases = intervals of length 1 (sometimes 0).
Related problems: Palindromic substrings, Burst Balloons, Coin Game (interval-based).
Statement: Given an array, find the length of the longest subsequence where every next element is strictly greater than the previous one.
Key Insight — why this is different from Pattern 1:
- In staircase problems, each state depended on exactly the last 2 states (constant).
- Here, to extend the sequence ending at the current element, you must check ALL previous elements — not a fixed number — because you don't know in advance which earlier element gives the best (longest) chain.
dp[i] = length of the longest increasing subsequence ENDING AT index i
Base case: dp[i] = 1 for all i (every element alone is a subsequence of length 1)
Transition:
for each i, for each j < i:
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
Answer: max(dp) (not necessarily the last element!)
Solution:
def lengthOfLIS(nums):
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)- Time: O(n²) (nested loop — outer over positions, inner over all previous candidates).
- Space: O(n).
⚠️ No memory optimization possible — everydp[i]might need ANY previousdp[j], so the whole array must be retained.- Note: An
O(n log n)solution exists using binary search, but that's a separate technique outside pure DP patterns.
Statement: Given an array and integer k, partition the array into contiguous subarrays of length at most k. Each element in a subarray becomes the subarray's max value. Maximize the total sum of the transformed array.
dp[i] = max sum achievable using the first i elements
for each i, try all partition lengths L from 1 to min(k, i):
maxInPartition = max of the last L elements ending at i
dp[i] = max(dp[i], dp[i-L] + maxInPartition * L)
Base case: dp[0] = 0
Answer: dp[n]
Solution:
def maxSumAfterPartitioning(arr, k):
n = len(arr)
dp = [0] * (n + 1)
for i in range(1, n + 1):
curMax = 0
for L in range(1, min(k, i) + 1):
curMax = max(curMax, arr[i - L])
dp[i] = max(dp[i], dp[i - L] + curMax * L)
return dp[n]- Time: O(n·k), Space: O(n).
dp[i]depends on a variable (potentially ALL) number of previous states, not a fixed count.- You must iterate over several/all previous candidates and pick the best (max/min).
- Results in a nested loop: outer over current position, inner over all valid candidates.
- Time complexity usually O(n²) (sometimes reducible with specialized data structures like binary search / segment trees).
- Memory optimization is usually impossible — you need access to all previous
dpvalues.
Related problems: Longest Bitonic Subsequence, Maximum Sum Increasing Subsequence, Box Stacking.
Statement: Given an array of positive integers, determine if it can be split into two subsets with equal sum.
Key Insight:
- Total sum must be even (if odd, impossible — return
Falseimmediately). - Target =
total_sum / 2. If we can find any subset that sums to exactlytarget, the remaining elements automatically form the other half. - This is the classic 0/1 Knapsack decision problem: "Can we exactly fill a knapsack of capacity
target?"
Data structure: A boolean array dp where index = a possible sum, value = True/False (is this sum reachable using elements processed so far).
dp[0] = True (sum 0 is always reachable — take nothing)
For each num in array:
For s from target down to num: # ⚠️ MUST go right-to-left!
dp[s] = dp[s] OR dp[s - num]
Answer: dp[target]
Solution:
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]
return dp[target]- Time: O(n · target) =
O(n · sum). - Space: O(target) =
O(sum).
Statement: Given coin denominations and a target amount, find the minimum number of coins needed to make that amount (coins can be reused/unlimited supply).
dp[a] = minimum coins needed to make amount a
dp[0] = 0
for a from 1 to amount:
for coin in coins:
if coin <= a:
dp[a] = min(dp[a], dp[a - coin] + 1)
Answer: dp[amount] if reachable, else -1
Note: Here we loop left to right (amount increasing) because coins can be reused unlimited times (unlike the subset-sum problem where each element is used at most once).
Solution:
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1- Time: O(n · amount) where
n= number of coin denominations. - Space: O(amount).
- Need to build a specific sum, or check if a target value is reachable, using array elements.
- Each element usable a limited number of times (often exactly once — "0/1 Knapsack"), or unlimited times ("Unbounded Knapsack").
- Order of elements doesn't matter — only the combination/multiset matters.
dparray where index = possible sum, value = reachability (bool) or optimal count (min/max).- Iteration direction matters:
- Right-to-left (
target → num) → each element used at most once. - Left-to-right (
num → target) → element can be used unlimited times.
- Right-to-left (
Related problems: Target Sum, Last Stone Weight II, Ones and Zeroes.
| Pattern | Signal in Problem Statement | Table Shape | Fill Order | Space Optimizable? |
|---|---|---|---|---|
| 1. Constant Transition | "reach step n," fixed small lookback | 1D array | Left → right | ✅ Yes → O(1) (few rolling vars) |
| 2. Grid DP | Explicit m×n grid, restricted movement | 2D array | Row by row (top→bottom) | ✅ Yes → O(n) or O(min(m,n)) |
| 3. Two Sequences | Two strings/arrays to compare | 2D array (len1+1 × len2+1) | Row by row | ✅ Yes → O(n) (2 rows) |
| 4. Interval DP | One sequence, need best answer over [i,j] |
2D array (n×n) | By interval length (short→long) | ✅ Yes → O(n) (2 rows, filled bottom-up) |
| 5. Non-Constant Transition | "longest increasing...", "must check all previous" | 1D array | Left → right, inner loop over ALL previous | ❌ No — need full array |
| 6. Knapsack-Like | "reach a target sum," "partition into equal sums," "fewest coins" | 1D array, index = sum | Depends on reuse rule (see below) | ✅ Yes → O(target) |
Knapsack direction rule:
- Each item used once → loop sums right to left.
- Each item reusable unlimited times → loop sums left to right.
| # | Problem | Pattern | Time | Space (optimized) |
|---|---|---|---|---|
| 1 | Climbing Stairs (count ways) | Constant Transition | O(n) | O(1) |
| 2 | N-th Tribonacci Number | Constant Transition | O(n) | O(1) |
| 3 | Min Cost Climbing Stairs | Constant Transition | O(n) | O(1) |
| 4 | House Robber | Constant Transition | O(n) | O(1) |
| 5 | Unique Paths | Grid DP | O(m·n) | O(n) |
| 6 | Unique Paths II (obstacles) | Grid DP | O(m·n) | O(n) |
| 7 | Longest Common Subsequence | Two Sequences | O(m·n) | O(n) |
| 8 | Edit Distance | Two Sequences | O(m·n) | O(n) |
| 9 | Longest Palindromic Subsequence | Interval DP | O(n²) | O(n) |
| 10 | Palindromic Substrings (count) | Interval DP (recursive) | O(n²) | O(n²) |
| 11 | Longest Increasing Subsequence | Non-Constant Transition | O(n²) | O(n) — not reducible |
| 12 | Partition Array for Maximum Sum | Non-Constant Transition | O(n·k) | O(n) |
| 13 | Partition Equal Subset Sum | Knapsack-Like | O(n·sum) | O(sum) |
| 14 | Coin Change (min coins) | Knapsack-Like | O(n·amount) | O(amount) |
- DP problems always reduce to: define the state → find the base case(s) → find the recurrence/transition → decide fill order → (optionally) optimize space.
- Naive recursive brute force is (almost) always exponential (
O(2^n)) — the presence of overlapping subproblems is the signal that DP applies. - Memoization vs. Tabulation is a code-style choice — both hit the same optimized time complexity; pick tabulation when the fill order is obvious, memoization when it's a partition-style problem or the order is unclear.
- Recognizing the pattern is 90% of the battle — once you know it's "Grid DP" or "Knapsack-like," the recurrence follows naturally from the problem's rules.
- Practice each pattern with 2-3 problems until the recurrence "formula" becomes second nature — that's what actually gets tested in interviews.