Dynamic Programming - Complete Placement Interview Question Bank

Last Updated: March 2026

---

Introduction: Why Dynamic Programming Matters in Coding Interviews

Dynamic Programming (DP) is the crown jewel of algorithmic problem-solving and the topic that separates good programmers from great ones. It appears in 30-35% of interviews at top-tier companies like Google, Facebook, Amazon, and Microsoft.

DP tests your ability to:

• Break down complex problems into simpler subproblems
• Recognize patterns and overlapping subproblems
• Optimize solutions from exponential to polynomial time
• Think recursively and iteratively

Mastering DP demonstrates that you can solve problems that seem impossible at first glance—a crucial skill for senior engineering roles.

---

Key Concepts and Theory

1. What is Dynamic Programming?

Dynamic Programming is an optimization technique for solving problems by breaking them into smaller subproblems and storing their solutions to avoid redundant computation.

Key Requirements:

1. Optimal Substructure: Optimal solution can be constructed from optimal solutions to subproblems
2. Overlapping Subproblems: Same subproblems are solved multiple times

2. DP Approaches

TOP-DOWN (Memoization):
├── Start with original problem
├── Break into subproblems recursively
├── Store solutions in memo/cache
└── Check memo before computing

BOTTOM-UP (Tabulation):
├── Start with smallest subproblems
├── Fill table iteratively
├── Build up to original problem
└── Often more space efficient

3. The DP Framework

STEP 1: Define State
   - What does dp[i] or dp[i][j] represent?

STEP 2: Formulate Recurrence
   - How to compute dp[i] from previous states?

STEP 3: Initialize Base Cases
   - What are the simplest subproblems?

STEP 4: Determine Order
   - What order to fill the table?

STEP 5: Extract Answer
   - Where is the final answer stored?

---

Time/Space Complexity Cheat Sheet

┌─────────────────────────────────────────────────────────────┐
│ DP COMPLEXITY PATTERNS                                      │
├─────────────────────────────────────────────────────────────┤
│ 1D DP with O(1) transition  │ O(n) time, O(n) space        │
│ 1D DP space optimized         │ O(n) time, O(1) space        │
│ 2D DP (grid/matrix)          │ O(n²) time, O(n²) space      │
│ 2D DP space optimized         │ O(n²) time, O(n) space       │
│ Knapsack (items × capacity)   │ O(n×W) time, O(n×W) space    │
│ Knapsack space optimized      │ O(n×W) time, O(W) space      │
│ Interval DP                   │ O(n²) or O(n³) time          │
│ Bitmask DP                    │ O(2^n × n) time              │
│ Tree DP                       │ O(n) time, O(h) space        │
└─────────────────────────────────────────────────────────────┘

---

DP Patterns

Pattern 1: Fibonacci Style

• Problems: Climbing Stairs, House Robber, Jump Game
• Recurrence: dp[i] = dp[i-1] + dp[i-2] (or similar)

Pattern 2: 0/1 Knapsack

• Problems: Subset Sum, Partition Equal Subset Sum, Target Sum
• Recurrence: dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]])

Pattern 3: Unbounded Knapsack

• Problems: Coin Change, Coin Change II, Perfect Squares
• Recurrence: dp[w] = min/max(dp[w], dp[w-coin] + 1)

Pattern 4: Longest Common Subsequence (LCS)

• Problems: LCS, Edit Distance, Longest Palindromic Subsequence
• Recurrence: dp[i][j] = dp[i-1][j-1] + 1 if match, else max(dp[i-1][j], dp[i][j-1])

Pattern 5: Palindromes

• Problems: Longest Palindromic Substring, Palindromic Partitioning
• Recurrence: Expand around center or dp[i][j] = dp[i+1][j-1] && s[i]==s[j]

Pattern 6: Decision Making

• Problems: House Robber II, Best Time to Buy/Sell Stock, Jump Game
• Recurrence: Choose best among options at each step

---

Practice Questions with Solutions

Question 1: Climbing Stairs (EASY ⭐)

Problem: Count ways to climb n stairs, taking 1 or 2 steps at a time.

Solution:

def climb_stairs(n):
    """
    Fibonacci pattern - O(n) time, O(1) space
    
    dp[i] = ways to reach step i
    dp[i] = dp[i-1] + dp[i-2]
    """
    if n <= 2:
        return n
    
    # Space optimized - only need last two values
    prev2, prev1 = 1, 2
    
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

# Full DP table version
def climb_stairs_dp(n):
    if n <= 2:
        return n
    
    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]

---

Question 2: House Robber (MEDIUM ⭐⭐)

Problem: Max money from houses without robbing adjacent houses.

Solution:

def rob(nums):
    """
    Decision making DP - O(n) time, O(1) space
    
    dp[i] = max money up to house i
    dp[i] = max(dp[i-1], nums[i] + dp[i-2])
    """
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)
    
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        current = max(prev1, nums[i] + prev2)
        prev2 = prev1
        prev1 = current
    
    return prev1

# With DP array (easier to understand)
def rob_dp(nums):
    if not nums:
        return 0
    
    n = len(nums)
    dp = [0] * (n + 1)
    dp[1] = nums[0]
    
    for i in range(2, n + 1):
        dp[i] = max(dp[i-1], nums[i-1] + dp[i-2])
    
    return dp[n]

---

Question 3: Coin Change (MEDIUM ⭐⭐)

Problem: Minimum coins needed to make amount (infinite supply).

Solution:

def coin_change(coins, amount):
    """
    Unbounded knapsack - O(n × amount) time, O(amount) space
    
    dp[i] = min coins to make amount i
    dp[i] = min(dp[i], dp[i-coin] + 1) for all coins
    """
    # Initialize with infinity
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 coins needed for amount 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# Alternative: iterate coins first
def coin_change_alternative(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

---

Question 4: Longest Increasing Subsequence (MEDIUM ⭐⭐)

Problem: Find length of longest strictly increasing subsequence.

Solution:

def length_of_lis(nums):
    """
    DP with binary search optimization - O(n log n) time, O(n) space
    
    tails[i] = smallest tail of increasing subsequence of length i+1
    """
    tails = []
    
    for num in nums:
        # Binary search for position to replace
        left, right = 0, len(tails)
        
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        
        if left == len(tails):
            tails.append(num)  # Extend longest subsequence
        else:
            tails[left] = num  # Replace to allow more future growth
    
    return len(tails)

# Classic O(n²) DP
def length_of_lis_dp(nums):
    if not nums:
        return 0
    
    n = len(nums)
    dp = [1] * n  # Each element is LIS of length 1
    
    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)

---

Question 5: Longest Common Subsequence (MEDIUM ⭐⭐)

Problem: Find length of longest subsequence common to both strings.

Solution:

def longest_common_subsequence(text1, text2):
    """
    Classic 2D DP - O(m × n) time, O(min(m,n)) space
    
    dp[i][j] = LCS of text1[0:i] and text2[0:j]
    """
    m, n = len(text1), len(text2)
    
    # Space optimized - only need previous row
    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  # Swap rows
    
    return prev[n]

# Full DP table with reconstruction
def lcs_with_reconstruction(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill table
    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])
    
    # Reconstruct LCS
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            lcs.append(text1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(lcs))

---

Question 6: Edit Distance (HARD ⭐⭐⭐)

Problem: Minimum operations (insert, delete, replace) to convert word1 to word2.

Solution:

def min_distance(word1, word2):
    """
    2D DP - O(m × n) time, O(min(m,n)) space
    
    dp[i][j] = edit distance between word1[0:i] and word2[0:j]
    """
    m, n = len(word1), len(word2)
    
    # Space optimized
    prev = list(range(n + 1))  # dp[0][j] = j (insert j chars)
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        curr[0] = i  # dp[i][0] = i (delete i chars)
        
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                curr[j] = prev[j-1]  # No operation needed
            else:
                # min(insert, delete, replace)
                curr[j] = 1 + min(curr[j-1],    # Insert
                                 prev[j],      # Delete
                                 prev[j-1])    # Replace
        
        prev, curr = curr, prev
    
    return prev[n]

---

Question 7: 0/1 Knapsack (MEDIUM ⭐⭐)

Problem: Maximize value with weight constraint (each item used at most once).

Solution:

def knapsack(weights, values, capacity):
    """
    0/1 Knapsack - O(n × capacity) time, O(capacity) space
    
    dp[w] = max value achievable with capacity w
    """
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # Iterate backwards to prevent reuse
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    
    return dp[capacity]

# With item tracking
def knapsack_with_items(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(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w],
                              values[i-1] + dp[i-1][w - weights[i-1]])
            else:
                dp[i][w] = dp[i-1][w]
    
    # Backtrack to find items
    items = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            items.append(i - 1)
            w -= weights[i-1]
    
    return dp[n][capacity], items

---

Question 8: Partition Equal Subset Sum (MEDIUM ⭐⭐)

Problem: Determine if array can be partitioned into two subsets with equal sum.

Solution:

def can_partition(nums):
    """
    0/1 Knapsack variation - O(n × sum) time, O(sum) space
    
    Goal: Find subset with sum = total_sum / 2
    """
    total = sum(nums)
    
    # Odd sum can't be partitioned equally
    if total % 2 != 0:
        return False
    
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        # Backwards to prevent reuse
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]
    
    return dp[target]

---

Question 9: Target Sum (MEDIUM ⭐⭐)

Problem: Assign + or - to each number to reach target sum.

Solution:

def find_target_sum_ways(nums, target):
    """
    Transform to subset sum - O(n × sum) time, O(sum) space
    
    Key: P - N = target, P + N = sum
         2P = target + sum
         P = (target + sum) / 2
    """
    total = sum(nums)
    
    # Check if possible
    if abs(target) > total or (target + total) % 2 != 0:
        return 0
    
    subset_sum = (target + total) // 2
    
    dp = [0] * (subset_sum + 1)
    dp[0] = 1  # One way to make sum 0
    
    for num in nums:
        for i in range(subset_sum, num - 1, -1):
            dp[i] += dp[i - num]
    
    return dp[subset_sum]

---

Question 10: Longest Palindromic Substring (MEDIUM ⭐⭐)

Problem: Find longest palindromic substring.

Solution:

def longest_palindrome(s):
    """
    Expand around center - O(n²) time, O(1) space
    
    Better than DP for this problem
    """
    if not s:
        return ""
    
    start = end = 0
    
    for i in range(len(s)):
        # Odd length palindromes
        len1 = expand_around_center(s, i, i)
        # Even length palindromes
        len2 = expand_around_center(s, i, i + 1)
        
        max_len = max(len1, len2)
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
    
    return s[start:end + 1]

def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

# DP approach
def longest_palindrome_dp(s):
    """
    DP - O(n²) time, O(n²) space
    """
    n = len(s)
    if n < 2:
        return s
    
    # dp[i][j] = s[i:j+1] is palindrome
    dp = [[False] * n for _ in range(n)]
    
    start = 0
    max_len = 1
    
    # Single characters are palindromes
    for i in range(n):
        dp[i][i] = True
    
    # Check substrings
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if length == 2:
                dp[i][j] = (s[i] == s[j])
            else:
                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
            
            if dp[i][j] and length > max_len:
                start = i
                max_len = length
    
    return s[start:start + max_len]

---

Question 11: Unique Paths (MEDIUM ⭐⭐)

Problem: Count unique paths from top-left to bottom-right in grid.

Solution:

def unique_paths(m, n):
    """
    Grid DP - O(m × n) time, O(n) space
    
    dp[i][j] = paths to reach (i, j)
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
    """
    # Space optimized - only need previous row
    dp = [1] * n  # First row: all 1s
    
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    
    return dp[-1]

# Math solution - O(min(m,n)) time
def unique_paths_math(m, n):
    """
    C(m+n-2, m-1) = (m+n-2)! / ((m-1)! × (n-1)!)
    """
    from math import comb
    return comb(m + n - 2, min(m - 1, n - 1))

---

Question 12: Minimum Path Sum (MEDIUM ⭐⭐)

Problem: Find path from top-left to bottom-right with minimum sum.

Solution:

def min_path_sum(grid):
    """
    Grid DP - O(m × n) time, O(n) space
    
    dp[i][j] = min path sum to reach (i, j)
    """
    if not grid or not grid[0]:
        return 0
    
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[j] = grid[i][j]
            elif i == 0:
                dp[j] = dp[j-1] + grid[i][j]
            elif j == 0:
                dp[j] = dp[j] + grid[i][j]
            else:
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
    
    return dp[-1]

---

Question 13: Decode Ways (MEDIUM ⭐⭐)

Problem: Count ways to decode digits to letters (A=1, B=2, ..., Z=26).

Solution:

def num_decodings(s):
    """
    DP - O(n) time, O(1) space
    
    dp[i] = ways to decode s[0:i]
    """
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    # dp[i-2], dp[i-1], dp[i]
    prev2, prev1 = 1, 1
    
    for i in range(1, n):
        current = 0
        
        # Single digit (if not '0')
        if s[i] != '0':
            current += prev1
        
        # Two digits (10-26)
        two_digit = int(s[i-1:i+1])
        if 10 <= two_digit <= 26:
            current += prev2
        
        prev2, prev1 = prev1, current
    
    return prev1

---

Question 14: Word Break (MEDIUM ⭐⭐)

Problem: Determine if string can be segmented into dictionary words.

Solution:

def word_break(s, word_dict):
    """
    DP - O(n² × m) time, O(n) space
    n = len(s), m = average word length
    
    dp[i] = s[0:i] can be segmented
    """
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

# Optimized with max word length
def word_break_optimized(s, word_dict):
    word_set = set(word_dict)
    max_len = max(len(w) for w in word_dict) if word_dict else 0
    
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

---

Question 15: Maximum Subarray (Kadane's) (EASY ⭐)

Problem: Find contiguous subarray with largest sum.

Solution:

def max_subarray(nums):
    """
    Kadane's Algorithm - O(n) time, O(1) space
    
    dp[i] = max subarray sum ending at i
    """
    if not nums:
        return 0
    
    max_ending_here = max_so_far = nums[0]
    
    for num in nums[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# With start and end indices
def max_subarray_indices(nums):
    if not nums:
        return 0, 0, 0
    
    max_sum = curr_sum = nums[0]
    start = end = temp_start = 0
    
    for i in range(1, len(nums)):
        if curr_sum + nums[i] < nums[i]:
            curr_sum = nums[i]
            temp_start = i
        else:
            curr_sum += nums[i]
        
        if curr_sum > max_sum:
            max_sum = curr_sum
            start = temp_start
            end = i
    
    return max_sum, start, end

---

Question 16: Best Time to Buy/Sell Stock with Cooldown (MEDIUM ⭐⭐)

Problem: Max profit with 1-day cooldown after selling.

Solution:

def max_profit(prices):
    """
    State machine DP - O(n) time, O(1) space
    
    States:
    - hold: max profit holding stock
    - sold: max profit just sold
    - rest: max profit in cooldown/rest
    """
    if not prices:
        return 0
    
    n = len(prices)
    hold, sold, rest = -prices[0], 0, 0
    
    for i in range(1, n):
        prev_sold = sold
        # Update states
        hold = max(hold, rest - prices[i])  # Buy or keep holding
        sold = hold + prices[i]              # Sell
        rest = max(rest, prev_sold)          # Cooldown or stay resting
    
    return max(sold, rest)

---

Question 17: Regular Expression Matching (HARD ⭐⭐⭐)

Problem: Implement regex matching with '.' and '*' support.

Solution:

def is_match(s, p):
    """
    2D DP - O(m × n) time, O(n) space
    
    dp[i][j] = s[0:i] matches p[0:j]
    """
    m, n = len(s), len(p)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty matches empty
    
    # Handle patterns like a*, a*b*, etc.
    for j in range(2, n + 1):
        dp[j] = dp[j-2] and p[j-1] == '*'
    
    for i in range(1, m + 1):
        new_dp = [False] * (n + 1)
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # Match zero or more of previous char
                new_dp[j] = new_dp[j-2]  # Zero occurrences
                if p[j-2] == '.' or p[j-2] == s[i-1]:
                    new_dp[j] = new_dp[j] or dp[j]  # One or more
            elif p[j-1] == '.' or p[j-1] == s[i-1]:
                new_dp[j] = dp[j-1]
        dp = new_dp
    
    return dp[n]

---

Question 18: Burst Balloons (HARD ⭐⭐⭐)

Problem: Burst balloons to maximize coins (interval DP).

Solution:

def max_coins(nums):
    """
    Interval DP - O(n³) time, O(n²) space
    
    dp[i][j] = max coins from bursting balloons in (i, j) exclusive
    """
    # Add virtual balloons with value 1 at boundaries
    nums = [1] + nums + [1]
    n = len(nums)
    
    dp = [[0] * n for _ in range(n)]
    
    # Length of interval
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            # Try bursting each balloon last
            for i in range(left + 1, right):
                coins = nums[left] * nums[i] * nums[right]
                coins += dp[left][i] + dp[i][right]
                dp[left][right] = max(dp[left][right], coins)
    
    return dp[0][n-1]

---

Question 19: Distinct Subsequences (HARD ⭐⭐⭐)

Problem: Count distinct subsequences of s that equal t.

Solution:

def num_distinct(s, t):
    """
    2D DP - O(m × n) time, O(n) space
    
    dp[i][j] = count of distinct subsequences of s[0:i] equal to t[0:j]
    """
    m, n = len(s), len(t)
    
    if n > m:
        return 0
    
    # dp[j] = count for t[0:j]
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty string has one subsequence
    
    for i in range(1, m + 1):
        # Traverse backwards to avoid using updated values
        for j in range(min(i, n), 0, -1):
            if s[i-1] == t[j-1]:
                dp[j] += dp[j-1]
    
    return dp[n]

---

Question 20: Palindromic Partitioning II (HARD ⭐⭐⭐)

Problem: Min cuts needed for palindrome partitioning.

Solution:

def min_cut(s):
    """
    DP - O(n²) time, O(n²) space
    
    dp[i] = min cuts for s[0:i+1]
    pal[i][j] = s[i:j+1] is palindrome
    """
    n = len(s)
    
    # Precompute palindromes
    pal = [[False] * n for _ in range(n)]
    
    for i in range(n):
        pal[i][i] = True
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if length == 2:
                pal[i][j] = (s[i] == s[j])
            else:
                pal[i][j] = (s[i] == s[j]) and pal[i+1][j-1]
    
    # Min cuts DP
    dp = [float('inf')] * n
    
    for i in range(n):
        if pal[0][i]:
            dp[i] = 0
        else:
            for j in range(i):
                if pal[j+1][i]:
                    dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[n-1]

# Optimized single DP
def min_cut_optimized(s):
    n = len(s)
    dp = [i for i in range(n)]  # Max cuts = i
    
    for center in range(n):
        # Odd length
        left = right = center
        while left >= 0 and right < n and s[left] == s[right]:
            new_cut = 0 if left == 0 else dp[left-1] + 1
            dp[right] = min(dp[right], new_cut)
            left -= 1
            right += 1
        
        # Even length
        left, right = center, center + 1
        while left >= 0 and right < n and s[left] == s[right]:
            new_cut = 0 if left == 0 else dp[left-1] + 1
            dp[right] = min(dp[right], new_cut)
            left -= 1
            right += 1
    
    return dp[n-1]

---

Common Interview Follow-up Questions

1. "Can you optimize the space?"

   • Most DP solutions can be space-optimized
   • Rolling array technique for 2D → 1D
   • Only keep necessary previous states

2. "What if we need to return the actual solution, not just the value?"

   • Backtrack through DP table
   • Store choices during DP computation
   • Reconstruct path from stored information

3. "How would you solve this with memoization instead?"

   • Top-down recursive approach
   • Hash map for memo instead of array
   • Often more intuitive but may have recursion overhead

4. "Can this be parallelized?"

   • Grid DP: process anti-diagonals in parallel
   • Some problems have inherent dependencies preventing parallelism

5. "What about negative numbers/constraints?"

   • Shift indices to handle negative
   • Use hash map DP for sparse states
   • Check for integer overflow

---

Companies That Frequently Ask DP

Company	Frequency	Common Questions
Google	⭐⭐⭐⭐⭐	Edit Distance, Regex Matching, Burst Balloons
Amazon	⭐⭐⭐⭐⭐	Coin Change, LIS, Word Break, House Robber
Microsoft	⭐⭐⭐⭐	LCS, Knapsack, Unique Paths, Decode Ways
Meta	⭐⭐⭐⭐	Target Sum, Palindromic Partitioning, LCS
Apple	⭐⭐⭐	Climbing Stairs, Maximum Subarray, Stock Problems
Netflix	⭐⭐⭐	Interval DP, Sequence alignment problems
Uber	⭐⭐⭐	Path finding, Minimum cost problems
Adobe	⭐⭐⭐	String DP, Palindrome problems

---

Preparation Tips for DP Problems

1. Master the Framework: State → Recurrence → Base Case → Order → Answer

2. Start with Recursive: Write recursive solution first, then add memoization, then convert to iterative

3. Draw the Table: For 2D DP, draw the table and fill a few cells manually to understand the pattern

4. Recognize Patterns: Knapsack, LCS, Palindromes, Grid paths—each has a recognizable structure

5. Practice Space Optimization: Know how to reduce from 2D to 1D when possible

6. Edge Cases: Empty inputs, single elements, all same values, negative numbers

7. Time Yourself: DP problems often take longer—aim to solve medium problems in 20-25 minutes

---

Frequently Asked Questions (FAQ)

Q1: How do I know if a problem can be solved with DP?

A: Check for:

• Optimal substructure: Optimal solution contains optimal sub-solutions
• Overlapping subproblems: Same subproblems solved multiple times
• Counting/optimization: Problems asking for "maximum", "minimum", "count", "ways"

Q2: Top-down vs Bottom-up—which should I use?

A:

• Top-down (memoization): More intuitive, easier to write, only computes needed states
• Bottom-up (tabulation): No recursion overhead, often more space-efficient, guaranteed no stack overflow
• Interview tip: Start with top-down, mention bottom-up optimization

Q3: How do I optimize space in DP?

A:

• Rolling array: If dp[i] only depends on dp[i-1], keep only 2 rows
• In-place updates: Some grid problems allow modifying input
• State compression: Use bitmasks or hash maps for sparse states

Q4: What's the difference between greedy and DP?

A: Greedy makes locally optimal choices hoping for global optimum (faster, doesn't always work). DP explores all possibilities and chooses best (slower, always optimal). When greedy fails, use DP.

Q5: How do I handle DP with large constraints?

A:

• Matrix exponentiation: For linear recurrences (O(log n))
• Monotonic queue optimization: For sliding window DP
• Convex hull trick: For DP with special structure
• Divide and conquer optimization: For certain DP forms

---

Quick Reference: DP Patterns

┌────────────────────────────────────────────────────────────────┐
│ PATTERN             │ STATE DEFINITION                         │
├────────────────────────────────────────────────────────────────┤
│ Fibonacci           │ dp[i] = dp[i-1] + dp[i-2]                │
│ 0/1 Knapsack        │ dp[i][w] = max with/without item i       │
│ Unbounded Knapsack  │ dp[w] = min/max using any item           │
│ LCS                 │ dp[i][j] = longest of s1[0:i], s2[0:j]   │
│ Grid Path           │ dp[i][j] = paths/sum to reach (i,j)      │
│ Interval DP         │ dp[i][j] = optimal for interval [i,j]    │
│ State Machine       │ Multiple states with transitions         │
│ Tree DP             │ dp[node] = optimal for subtree           │
│ Bitmask DP          │ dp[mask] = optimal for subset mask       │
└────────────────────────────────────────────────────────────────┘

---

Dynamic Programming: Where subproblems meet solutions! 🧩