Dynamic Programming - Complete DSA Guide
Table of Contents
1. Introduction
2. Dynamic Programming Fundamentals
3. DP Approaches
4. Classic DP Problems
5. DP Patterns
6. String DP Problems
7. Tree and Graph DP
8. Optimization Techniques
9. Time & Space Complexity
10. Practice Problems
Introduction
Dynamic Programming (DP) is a powerful algorithmic paradigm that solves complex problems by
breaking them down into simpler subproblems. It combines the efficiency of greedy algorithms with the
correctness of exhaustive search.
Why Dynamic Programming Matters
• Optimization: Significantly reduces time complexity
• Problem Solving: Essential for many algorithmic challenges
• Real Applications: Used in economics, bioinformatics, AI, and more
• Interview Frequency: Very common in technical interviews
• Mathematical Foundation: Builds strong analytical thinking
Dynamic Programming Fundamentals
Core Concepts
1. Optimal Substructure
A problem has optimal substructure if an optimal solution contains optimal solutions to subproblems.
python
# Example: Fibonacci sequence
# F(n) = F(n-1) + F(n-2)
# Optimal solution for F(n) uses optimal solutions for F(n-1) and F(n-2)
2. Overlapping Subproblems
The same subproblems are solved multiple times in a naive recursive approach.
python
# Fibonacci without DP - exponential time
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
# Many subproblems calculated multiple times:
# fib(5) calls fib(4) and fib(3)
# fib(4) calls fib(3) and fib(2)
# fib(3) is calculated twice!
3. Memoization
Store results of expensive function calls to avoid recomputation.
python
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
4. Tabulation
Build up solutions from smaller subproblems systematically.
python
def fib_tabulation(n):
if n <= 1:
return 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]
DP Approaches
1. Top-Down (Memoization)
• Start with the original problem
• Recursively break down into subproblems
• Store results to avoid recomputation
Template:
python
def dp_top_down(params, memo={}):
# Base case
if base_condition:
return base_value
# Check if already computed
if params in memo:
return memo[params]
# Recursive computation
result = compute_from_subproblems()
memo[params] = result
return result
2. Bottom-Up (Tabulation)
• Start with smallest subproblems
• Build up to larger problems
• Usually more space efficient
Template:
python
def dp_bottom_up(n):
# Initialize DP table
dp = [0] * (n + 1)
# Base cases
dp[0] = base_value
# Fill table
for i in range(1, n + 1):
dp[i] = compute_from_previous(dp, i)
return dp[n]
Classic DP Problems
1. Climbing Stairs
Problem: How many ways to reach the top of n stairs if you can climb 1 or 2 steps at a time?
python
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# Space optimized version
def climb_stairs_optimized(n):
if n <= 2:
return n
prev2 = 1 # dp[i-2]
prev1 = 2 # dp[i-1]
for i in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
2. House Robber
Problem: Rob houses to maximize money without robbing adjacent houses.
python
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[n-1]
# Space optimized
def rob_optimized(nums):
if not nums:
return 0
prev2 = 0 # dp[i-2]
prev1 = 0 # dp[i-1]
for num in nums:
current = max(prev1, prev2 + num)
prev2 = prev1
prev1 = current
return prev1
3. 0/1 Knapsack Problem
Problem: Maximize value in knapsack with weight constraint.
python
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
# Don't take item i-1
dp[i][w] = dp[i-1][w]
# Take item i-1 if it fits
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
# Space optimized (1D array)
def knapsack_1d(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# Traverse backwards to avoid using updated values
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
4. Coin Change
Problem: Find minimum coins to make target amount.
python
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Count number of ways to make amount
def coin_change_ways(coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
5. Longest Increasing Subsequence (LIS)
Problem: Find length of longest increasing subsequence.
python
def lis_dp(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# Binary search approach - O(n log n)
def lis_binary_search(nums):
import bisect
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
DP Patterns
1. Linear DP
Problems where state depends on previous states in a linear fashion.
Examples: Fibonacci, Climbing Stairs, House Robber
Template:
python
def linear_dp(arr):
n = len(arr)
dp = [0] * n
# Base cases
dp[0] = base_value
for i in range(1, n):
dp[i] = function_of(dp[i-1], arr[i])
return dp[n-1]
2. Grid DP
Problems involving 2D grids or matrices.
Example: Minimum Path Sum
python
def min_path_sum(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
# Base case
dp[0][0] = grid[0][0]
# Fill first row
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# Fill first column
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
# Fill rest of the table
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
3. Interval DP
Problems involving intervals or ranges.
Example: Matrix Chain Multiplication
python
def matrix_chain_multiplication(dimensions):
n = len(dimensions) - 1
dp = [[0] * n for _ in range(n)]
# Length of chain
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = (dp[i][k] + dp[k+1][j] +
dimensions[i] * dimensions[k+1] * dimensions[j+1])
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
4. Subset DP
Problems involving subsets or partitions.
Example: Partition Equal Subset Sum
python
def can_partition(nums):
total_sum = sum(nums)
if total_sum % 2 != 0:
return False
target = total_sum // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target]
5. State Machine DP
Problems with different states and transitions.
Example: Best Time to Buy and Sell Stock with Transaction Fee
python
def max_profit_with_fee(prices, fee):
hold = -prices[0] # Max profit when holding stock
sold = 0 # Max profit when not holding stock
for i in range(1, len(prices)):
hold = max(hold, sold - prices[i])
sold = max(sold, hold + prices[i] - fee)
return sold
String DP Problems
1. Longest Common Subsequence (LCS)
python
def lcs(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]
2. Edit Distance (Levenshtein Distance)
python
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base cases
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], # Delete
dp[i][j-1], # Insert
dp[i-1][j-1] # Replace
)
return dp[m][n]
3. Palindromic Subsequences
python
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
# Every single character is a palindrome
for i in range(n):
dp[i][i] = 1
# Fill for substrings of length 2 to n
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]
Tree and Graph DP
1. Tree DP - Maximum Path Sum
python
def max_path_sum(root):
max_sum = float('-inf')
def max_gain(node):
nonlocal max_sum
if not node:
return 0
# Max gain from left and right subtrees
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
# Price of new path including current node
price_new_path = node.val + left_gain + right_gain
# Update global maximum
max_sum = max(max_sum, price_new_path)
# Return max gain if continue with this node
return node.val + max(left_gain, right_gain)
max_gain(root)
return max_sum
2. Graph DP - Longest Path in DAG
python
def longest_path_dag(graph):
in_degree = {node: 0 for node in graph}
# Calculate in-degrees
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
# Topological sort using Kahn's algorithm
from collections import deque
queue = deque([node for node in in_degree if in_degree[node] == 0])
dp = {node: 0 for node in graph}
max_path = 0
while queue:
node = queue.popleft()
for neighbor, weight in graph[node]:
dp[neighbor] = max(dp[neighbor], dp[node] + weight)
max_path = max(max_path, dp[neighbor])
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return max_path
Optimization Techniques
1. Space Optimization
Reduce space complexity by keeping only necessary previous states.
python
# From O(n) to O(1) space for Fibonacci
def fib_optimized(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
2. Memoization with Decorators
python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo_decorator(n):
if n <= 1:
return n
return fib_memo_decorator(n-1) + fib_memo_decorator(n-2)
3. Rolling Array Technique
python
def unique_paths_optimized(m, n):
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[n-1]
4. State Compression
For problems with multiple states, use bit manipulation to compress states.
python
def travel_salesman_dp(dist, n):
# dp[mask][i] = min cost to visit cities in mask ending at city i
dp = {}
def solve(mask, pos):
if mask == (1 << n) - 1:
return dist[pos][0] # Return to start
if (mask, pos) in dp:
return dp[(mask, pos)]
result = float('inf')
for city in range(n):
if not (mask & (1 << city)):
new_mask = mask | (1 << city)
result = min(result, dist[pos][city] + solve(new_mask, city))
dp[(mask, pos)] = result
return result
return solve(1, 0) # Start from city 0
Time & Space Complexity
Common DP Complexities
Problem Type Time Space Space Optimized
Linear DP O(n) O(n) O(1)
2D Grid DP O(mn) O(mn) O(min(m,n))
LCS O(mn) O(mn) O(min(m,n))
Knapsack O(nW) O(nW) O(W)
LIS O(n²) O(n) O(n)
LIS (Binary Search) O(n log n) O(n) O(n)
Matrix Chain O(n³) O(n²) O(n²)
Factors Affecting Complexity
• Number of states: How many unique subproblems
• State transitions: Cost to compute each state
• Overlapping: Degree of subproblem overlap
• Space optimization: Whether rolling arrays can be used
Practice Problems
Beginner Level
1. Min Cost Climbing Stairs
2. Maximum Subarray (Kadane's Algorithm)
3. Range Sum Query - Immutable
4. Pascal's Triangle
5. Unique Paths
Intermediate Level
1. Decode Ways
2. Word Break
3. Triangle (Minimum Path Sum)
4. Maximum Product Subarray
5. Coin Change 2
Advanced Level
1. Regular Expression Matching
2. Interleaving String
3. Distinct Subsequences
4. Maximum Rectangle
5. Burst Balloons
Expert Level
1. Shortest Superstring
2. Optimal Binary Search Tree
3. Palindrome Partitioning II
4. Count of Range Sum
5. Strange Printer
Tips for Success
Problem-Solving Strategy
1. Identify DP characteristics: Optimal substructure and overlapping subproblems
2. Define state: What does dp[i] or dp[i][j] represent?
3. Find recurrence relation: How to compute current state from previous states
4. Determine base cases: What are the simplest subproblems?
5. Choose approach: Top-down (memoization) or bottom-up (tabulation)
6. Optimize space: Can you reduce space complexity?
Common Patterns Recognition
• Optimization problems: Usually ask for minimum/maximum
• Counting problems: How many ways to do something
• Decision problems: Is it possible to achieve something
• Sequence problems: Often 1D DP
• Grid problems: Usually 2D DP
• Interval problems: Consider all possible splits
Common Pitfalls
• Not identifying the optimal substructure
• Incorrect base cases
• Wrong order of computation in tabulation
• Forgetting to handle edge cases
• Not optimizing space when possible
• Recursive solution without memoization leading to TLE
Best Practices
• Start with recursive solution, then add memoization
• Always handle edge cases first
• Use meaningful variable names for DP states
• Test with small examples first
• Consider both time and space complexity
• Practice state definition - it's often the hardest part
Advanced Tips
• Matrix exponentiation: For problems with linear recurrence
• Digit DP: For problems involving digit constraints
• Probability DP: For problems involving probabilities
• Bitmask DP: For problems involving subsets
• Tree DP: For problems on trees
• Profile DP: For problems on grids with constraints
Conclusion
Dynamic Programming is a powerful technique that transforms exponential-time recursive solutions into
polynomial-time algorithms. Success in DP requires:
1. Pattern Recognition: Identifying when DP applies
2. State Definition: Clearly defining what each DP state represents
3. Recurrence Relations: Finding the mathematical relationship between states
4. Implementation: Choosing between top-down and bottom-up approaches
5. Optimization: Reducing space complexity when possible
The key to mastering DP is practice and pattern recognition. Start with basic problems like Fibonacci and
Climbing Stairs, then gradually work your way up to more complex problems. Focus on understanding
the underlying principles rather than memorizing solutions.
Remember: DP is not just about the algorithm - it's about the way of thinking. Once you develop DP
intuition, you'll find that many seemingly complex problems have elegant DP solutions.
