🧩 Dynamic Programming
Solve complex problems by breaking them into overlapping subproblems. Master memoization, tabulation, and state transition design.
Overview
What is Dynamic Programming?
Key DP Algorithms
Fibonacci Sequence
Classic problem: compute nth Fibonacci number with memoization
Coin Change Problem
Minimum coins needed to make a target amount
Longest Common Subsequence
Find longest subsequence common to two strings
0/1 Knapsack
Maximize value with weight constraint
Edit Distance
Minimum operations to convert one string to another
Interactive Visualizer
DP Table Visualization
Fibonacci Sequence DP Table Visualizer
Watch how DP tables are filled row by row during the tabulation process.
Deep Dive: Fibonacci Sequence
Time Complexity
Time: O(n)Space Complexity
Space: O(n)Approach
Top-down + Bottom-upDP Pattern
python
# Memoization approach
def fib(n, memo = {}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
# Tabulation approach
def fibTab(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]Define State
What does dp[i] or dp[i][j] represent? This is the most important step.
Base Cases
Initialize dp[0], dp[0][0], etc. with known starting values.
State Transition
How does dp[i] relate to previous states? This is the recurrence relation.
Return Result
The answer is usually dp[n], dp[m][n], or the best value in the table.
Common DP Problems
Climbing Stairs
Easydp[i] = dp[i-1] + dp[i-2]
House Robber
MediumMax of adjacent or current + skip
Longest Increasing Subsequence
Mediumdp[i] = 1 + max(dp[j]) for j < i
Palindrome Substring
MediumExpand center or DP table
Word Break
Mediumdp[i] = can segment s[0:i]
Maximum Subarray
EasyKadane's algorithm: dp[i] = max(arr[i], dp[i-1] + arr[i])
Interview Questions
What's the difference between memoization and tabulation?
Memoization (top-down) uses recursion + cache. Easier to code from recurrence relation but may hit recursion limits. Tabulation (bottom-up) is iterative, often more efficient in space, and avoids recursion overhead. Both have same time complexity.
How do you identify if DP can be applied?
Look for: 1) Problem asks for optimum (min/max/longest/shortest), 2) Decisions affect future outcomes, 3) Overlapping subproblems - brute force recalculates same subproblems. Classic examples: Fibonacci, knapsack, LCS.
How do you optimize DP space?
Check if dp[i] depends only on dp[i-1] or few previous states. You can use 1D array instead of 2D (e.g., knapsack), or just a few variables (e.g., Fibonacci: just 2 vars). This is called 'rolling array' optimization.
Common Mistakes to Avoid
Starting with tabulation before understanding the recursive solution
Not defining base cases properly - the foundation of correct DP
Using too large a state space - carefully choose what to memoize
Forgetting to handle edge cases: empty input, single element, zero amount
Confusing top-down (memoization) with bottom-up (tabulation) approach