📊 DP Problems: 1D, 2D & Knapsack

Intermediate to Advanced ~45 min read

Now that you understand DP fundamentals, let's solve real problems! We'll explore 1D DP (single array), 2D DP (matrix/grid), and Knapsack problems - three essential DP patterns used in countless interviews and real-world applications.

Part 1: 1D DP Problems

1D DP uses a single array where dp[i] represents the answer for subproblem ending at index i.

House Robber Problem

Problem

You can't rob adjacent houses. Maximize total money robbed.

State: dp[i] = maximum money robbed up to house i

Transition: dp[i] = max(rob house i, skip house i) = max(dp[i-2] + houses[i], dp[i-1])

Coin Change

Two Variants

Minimum Coins: Fewest coins to make amount

Number of Ways: Total ways to make amount

Key insight: For each amount, try all coin choices

The Complete Code: 1D DP

"""
1D Dynamic Programming Problems
House Robber, Coin Change, and other single-array DP problems
"""

# ============================================================================
# HOUSE ROBBER
# ============================================================================

def house_robber(houses):
    """
    House Robber: Can't rob adjacent houses
    Maximize total money robbed
    
    dp[i] = maximum money robbed up to house i
    dp[i] = max(rob house i, skip house i)
           = max(dp[i-2] + houses[i], dp[i-1])
    """
    print(f"\n🏠 House Robber Problem")
    print(f"   Houses: {houses}")
    
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
    
    n = len(houses)
    dp = [0] * n
    dp[0] = houses[0]
    dp[1] = max(houses[0], houses[1])
    
    print(f"   dp[0] = {dp[0]} (rob house 0)")
    print(f"   dp[1] = max({houses[0]}, {houses[1]}) = {dp[1]}")
    
    for i in range(2, n):
        # Rob current house + best from 2 houses ago
        rob_current = dp[i - 2] + houses[i]
        # Skip current house, take best from previous house
        skip_current = dp[i - 1]
        dp[i] = max(rob_current, skip_current)
        print(f"   dp[{i}] = max(rob: {rob_current}, skip: {skip_current}) = {dp[i]}")
    
    print(f"\n✓ Maximum money: {dp[n - 1]}")
    return dp[n - 1]

def house_robber_optimized(houses):
    """Space-optimized: Only need last two values"""
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
    
    prev2, prev1 = houses[0], max(houses[0], houses[1])
    
    for i in range(2, len(houses)):
        current = max(prev2 + houses[i], prev1)
        prev2, prev1 = prev1, current
    
    return prev1

def house_robber_circular(houses):
    """
    House Robber II: Houses arranged in circle
    First and last houses are adjacent
    """
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
    
    # Two cases: Rob first (exclude last) or Skip first (can include last)
    return max(
        house_robber_optimized(houses[:-1]),  # Exclude last house
        house_robber_optimized(houses[1:])     # Exclude first house
    )

# ============================================================================
# COIN CHANGE (MINIMUM COINS)
# ============================================================================

def coin_change_min(coins, amount):
    """
    Coin Change: Minimum coins to make amount
    dp[i] = minimum coins to make amount i
    dp[i] = min(dp[i-coin] + 1) for coin in coins
    """
    print(f"\n💰 Coin Change (Minimum Coins)")
    print(f"   Coins: {coins}, Amount: {amount}")
    
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 coins to make amount 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
                print(f"   dp[{i}] = min(dp[{i}], dp[{i - coin}] + 1) = {dp[i]}")
    
    result = dp[amount] if dp[amount] != float('inf') else -1
    print(f"\n✓ Minimum coins: {result}")
    return result

# ============================================================================
# COIN CHANGE (NUMBER OF WAYS)
# ============================================================================

def coin_change_ways(coins, amount):
    """
    Coin Change: Number of ways to make amount
    dp[i] = number of ways to make amount i
    dp[i] = sum(dp[i-coin]) for coin in coins
    """
    print(f"\n💰 Coin Change (Number of Ways)")
    print(f"   Coins: {coins}, Amount: {amount}")
    
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make amount 0 (use no coins)
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
            print(f"   After coin {coin}: dp[{i}] = {dp[i]}")
    
    print(f"\n✓ Number of ways: {dp[amount]}")
    return dp[amount]

# ============================================================================
# DECODE WAYS
# ============================================================================

def decode_ways(s):
    """
    Decode Ways: 'A'=1, 'B'=2, ..., 'Z'=26
    How many ways to decode string?
    
    dp[i] = ways to decode string[0:i]
    """
    print(f"\n📝 Decode Ways")
    print(f"   String: {s}")
    
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty string = 1 way
    dp[1] = 1  # Single digit (if not '0')
    
    for i in range(2, n + 1):
        # Single digit
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]
        
        # Two digits
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i - 2]
        
        print(f"   dp[{i}] = {dp[i]}")
    
    print(f"\n✓ Ways to decode: {dp[n]}")
    return dp[n]

# ============================================================================
# LONGEST INCREASING SUBSEQUENCE (LIS)
# ============================================================================

def longest_increasing_subsequence(nums):
    """
    LIS: Longest strictly increasing subsequence
    dp[i] = length of LIS ending at index i
    dp[i] = max(dp[j] + 1) for j < i where nums[j] < nums[i]
    """
    print(f"\n📈 Longest Increasing Subsequence")
    print(f"   Array: {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)
        print(f"   dp[{i}] = {dp[i]} (LIS ending at index {i})")
    
    result = max(dp)
    print(f"\n✓ Length of LIS: {result}")
    return result

# ============================================================================
# PALINDROME PARTITIONING (MINIMUM CUTS)
# ============================================================================

def min_palindrome_cuts(s):
    """
    Minimum cuts to partition string into palindromes
    dp[i] = minimum cuts for string[0:i]
    """
    print(f"\n✂️ Minimum Palindrome Cuts")
    print(f"   String: {s}")
    
    n = len(s)
    dp = [0] * (n + 1)
    
    # Precompute palindrome table
    is_palindrome = [[False] * n for _ in range(n)]
    for i in range(n):
        is_palindrome[i][i] = True
    for i in range(n - 1):
        is_palindrome[i][i + 1] = (s[i] == s[i + 1])
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            is_palindrome[i][j] = (s[i] == s[j] and is_palindrome[i + 1][j - 1])
    
    # DP
    for i in range(1, n + 1):
        dp[i] = i - 1  # Worst case: cut after each character
        for j in range(i):
            if is_palindrome[j][i - 1]:
                dp[i] = min(dp[i], dp[j] + 1)
        print(f"   dp[{i}] = {dp[i]}")
    
    print(f"\n✓ Minimum cuts: {dp[n]}")
    return dp[n]

# ============================================================================
# EXAMPLE 1: House Robber
# ============================================================================

print("=" * 70)
print("Example 1: House Robber")
print("=" * 70)

houses1 = [2, 7, 9, 3, 1]
house_robber(houses1)

# ============================================================================
# EXAMPLE 2: Coin Change
# ============================================================================

print("\n" + "=" * 70)
print("Example 2: Coin Change")
print("=" * 70)

coins1 = [1, 3, 4]
amount1 = 6
coin_change_min(coins1, amount1)

# ============================================================================
# EXAMPLE 3: Decode Ways
# ============================================================================

print("\n" + "=" * 70)
print("Example 3: Decode Ways")
print("=" * 70)

decode_ways("226")

# ============================================================================
# EXAMPLE 4: LIS
# ============================================================================

print("\n" + "=" * 70)
print("Example 4: Longest Increasing Subsequence")
print("=" * 70)

nums1 = [10, 9, 2, 5, 3, 7, 101, 18]
longest_increasing_subsequence(nums1)

# ============================================================================
# COMPLEXITY ANALYSIS
# ============================================================================

print("\n" + "=" * 70)
print("Complexity Analysis")
print("=" * 70)

print(f"\n{'Problem':<30} {'Time':<20} {'Space':<20}")
print("─" * 70)
print(f"{'House Robber':<30} {'O(n)':<20} {'O(n) or O(1)'}")
print(f"{'Coin Change (min)':<30} {'O(amount × coins)':<20} {'O(amount)'}")
print(f"{'Coin Change (ways)':<30} {'O(amount × coins)':<20} {'O(amount)'}")
print(f"{'Decode Ways':<30} {'O(n)':<20} {'O(n)'}")
print(f"{'LIS':<30} {'O(n²)':<20} {'O(n)'}")

# ============================================================================
# KEY TAKEAWAYS
# ============================================================================

print("\n" + "=" * 70)
print("Key Takeaways")
print("=" * 70)

print("\n✓ 1D DP uses single array dp[i]")
print("✓ State: dp[i] = answer for subproblem ending/up to index i")
print("✓ Transition: dp[i] depends on previous dp[j] values")
print("✓ Common patterns: max/min, sum, count")
print("✓ House Robber: max(rob current, skip current)")
print("✓ Coin Change: min/sum over all coin choices")
print("✓ Space can often be optimized to O(1) if only need previous values")

Output

Click Run to execute your code

Part 2: 2D DP Problems

2D DP uses a matrix where dp[i][j] represents the answer at position (i, j) or for subproblem involving first i elements of sequence 1 and first j elements of sequence 2.

Longest Common Subsequence (LCS)

Problem

Find longest subsequence common to both strings.

State: dp[i][j] = LCS length of text1[0:i] and text2[0:j]

Transition: If match: dp[i][j] = dp[i-1][j-1] + 1, else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Edit Distance (Levenshtein)

Problem

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

Application: Spell checkers, DNA sequence alignment, fuzzy matching

Unique Paths

Robot can move right or down. How many paths from top-left to bottom-right?

Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]

The Complete Code: 2D DP

"""
2D Dynamic Programming Problems
LCS, Edit Distance, Unique Paths, and other matrix/grid DP problems
"""

# ============================================================================
# UNIQUE PATHS
# ============================================================================

def unique_paths(m, n):
    """
    Unique Paths: Robot at (0,0), can move right or down
    How many paths to (m-1, n-1)?
    
    dp[i][j] = paths to reach (i, j)
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
    """
    print(f"\n🛤️ Unique Paths")
    print(f"   Grid: {m}×{n}")
    
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    
    # First row: only right moves
    for j in range(1, n):
        dp[0][j] = 1
    
    # First column: only down moves
    for i in range(1, m):
        dp[i][0] = 1
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    print(f"\n✓ Unique paths: {dp[m - 1][n - 1]}")
    return dp[m - 1][n - 1]

def unique_paths_with_obstacles(grid):
    """
    Unique Paths II: Grid has obstacles (1 = obstacle, 0 = empty)
    dp[i][j] = paths to (i,j) avoiding obstacles
    """
    print(f"\n🛤️ Unique Paths with Obstacles")
    print(f"   Grid: {grid}")
    
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    # Base case: start position
    dp[0][0] = 1 if grid[0][0] == 0 else 0
    
    # First row
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] if grid[0][j] == 0 else 0
    
    # First column
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] if grid[i][0] == 0 else 0
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 0:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            else:
                dp[i][j] = 0
    
    print(f"\n✓ Unique paths: {dp[m - 1][n - 1]}")
    return dp[m - 1][n - 1]

# ============================================================================
# LONGEST COMMON SUBSEQUENCE (LCS)
# ============================================================================

def longest_common_subsequence(text1, text2):
    """
    LCS: Longest common subsequence between two strings
    
    dp[i][j] = LCS length of text1[0:i] and text2[0:j]
    dp[i][j] = dp[i-1][j-1] + 1 if text1[i-1] == text2[j-1]
             = max(dp[i-1][j], dp[i][j-1]) otherwise
    """
    print(f"\n📝 Longest Common Subsequence")
    print(f"   Text1: {text1}")
    print(f"   Text2: {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])
    
    print(f"\n✓ LCS length: {dp[m][n]}")
    return dp[m][n]

def lcs_reconstruct(text1, text2, dp):
    """Reconstruct LCS string from DP table"""
    i, j = len(text1), len(text2)
    lcs = []
    
    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))

# ============================================================================
# EDIT DISTANCE (LEVENSHTEIN)
# ============================================================================

def edit_distance(word1, word2):
    """
    Edit Distance: Minimum operations to convert word1 to word2
    Operations: Insert, Delete, Replace
    
    dp[i][j] = edit distance between word1[0:i] and word2[0:j]
    dp[i][j] = dp[i-1][j-1] if word1[i-1] == word2[j-1]
             = min(
                 dp[i-1][j] + 1,      # Delete from word1
                 dp[i][j-1] + 1,      # Insert into word1
                 dp[i-1][j-1] + 1     # Replace
               )
    """
    print(f"\n✏️ Edit Distance (Levenshtein)")
    print(f"   Word1: {word1}")
    print(f"   Word2: {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  # Delete all characters from word1
    for j in range(n + 1):
        dp[0][j] = j  # Insert all characters into word1
    
    # Fill DP table
    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] = min(
                    dp[i - 1][j] + 1,      # Delete
                    dp[i][j - 1] + 1,      # Insert
                    dp[i - 1][j - 1] + 1   # Replace
                )
    
    print(f"\n✓ Edit distance: {dp[m][n]}")
    return dp[m][n]

# ============================================================================
# MAXIMUM SQUARE IN MATRIX
# ============================================================================

def maximal_square(matrix):
    """
    Maximal Square: Largest square of 1s in binary matrix
    dp[i][j] = side length of largest square ending at (i, j)
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if matrix[i][j] == 1
             = 0 otherwise
    """
    print(f"\n⬜ Maximal Square")
    print(f"   Matrix: {matrix}")
    
    if not matrix:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    max_side = 0
    
    # First row and column
    for i in range(m):
        dp[i][0] = int(matrix[i][0])
        max_side = max(max_side, dp[i][0])
    for j in range(n):
        dp[0][j] = int(matrix[0][j])
        max_side = max(max_side, dp[0][j])
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == '1':
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                max_side = max(max_side, dp[i][j])
    
    area = max_side * max_side
    print(f"\n✓ Maximal square area: {area} (side: {max_side})")
    return area

# ============================================================================
# MINIMUM PATH SUM
# ============================================================================

def min_path_sum(grid):
    """
    Minimum Path Sum: Minimum sum path from top-left to bottom-right
    dp[i][j] = minimum sum to reach (i, j)
    dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    """
    print(f"\n📉 Minimum Path Sum")
    print(f"   Grid: {grid}")
    
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    # Base case
    dp[0][0] = grid[0][0]
    
    # First row
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    
    # First column
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    
    print(f"\n✓ Minimum path sum: {dp[m - 1][n - 1]}")
    return dp[m - 1][n - 1]

# ============================================================================
# EXAMPLE 1: Unique Paths
# ============================================================================

print("=" * 70)
print("Example 1: Unique Paths")
print("=" * 70)

unique_paths(3, 7)

# ============================================================================
# EXAMPLE 2: Longest Common Subsequence
# ============================================================================

print("\n" + "=" * 70)
print("Example 2: Longest Common Subsequence")
print("=" * 70)

text1 = "abcde"
text2 = "ace"
longest_common_subsequence(text1, text2)

# ============================================================================
# EXAMPLE 3: Edit Distance
# ============================================================================

print("\n" + "=" * 70)
print("Example 3: Edit Distance")
print("=" * 70)

edit_distance("horse", "ros")

# ============================================================================
# EXAMPLE 4: Minimum Path Sum
# ============================================================================

print("\n" + "=" * 70)
print("Example 4: Minimum Path Sum")
print("=" * 70)

grid1 = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
min_path_sum(grid1)

# ============================================================================
# COMPLEXITY ANALYSIS
# ============================================================================

print("\n" + "=" * 70)
print("Complexity Analysis")
print("=" * 70)

print(f"\n{'Problem':<30} {'Time':<25} {'Space'}")
print("─" * 75)
print(f"{'Unique Paths':<30} {'O(m × n)':<25} {'O(m × n)'}")
print(f"{'LCS':<30} {'O(m × n)':<25} {'O(m × n)'}")
print(f"{'Edit Distance':<30} {'O(m × n)':<25} {'O(m × n)'}")
print(f"{'Min Path Sum':<30} {'O(m × n)':<25} {'O(m × n)'}")
print(f"{'Maximal Square':<30} {'O(m × n)':<25} {'O(m × n)'}")

# ============================================================================
# KEY TAKEAWAYS
# ============================================================================

print("\n" + "=" * 70)
print("Key Takeaways")
print("=" * 70)

print("\n✓ 2D DP uses matrix dp[i][j]")
print("✓ State: dp[i][j] = answer for subproblem at position (i, j)")
print("✓ Common patterns: Path counting, matching, optimization on grid")
print("✓ Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]")
print("✓ LCS: Match (diagonal) or skip (left/up)")
print("✓ Edit Distance: min of insert, delete, replace")
print("✓ Think in terms of grid/matrix traversal")

Output

Click Run to execute your code

Part 3: Knapsack Problems

Knapsack problems involve selecting items with constraints (weight, value, capacity).

0/1 Knapsack

Problem

Each item can be taken at most once. Maximize value within weight capacity.

State: dp[i][w] = maximum value using first i items with capacity w

Transition: dp[i][w] = max(don't take: dp[i-1][w], take: dp[i-1][w-weight[i]] + value[i])

Unbounded Knapsack

Key Difference

Items can be taken unlimited times. Same as coin change problem!

Transition: dp[w] = max(dp[w-weight[i]] + value[i]) for all items

Subset Sum

Can we form target sum using subset of numbers? Boolean DP problem.

The Complete Code: Knapsack

"""
Knapsack Problems
0/1 Knapsack, Unbounded Knapsack, Subset Sum
"""

# ============================================================================
# 0/1 KNAPSACK
# ============================================================================

def knapsack_01(weights, values, capacity):
    """
    0/1 Knapsack: Each item can be taken at most once
    
    dp[i][w] = maximum value using first i items with capacity w
    dp[i][w] = max(
        dp[i-1][w],                    # Don't take item i
        dp[i-1][w-weights[i-1]] + values[i-1]  # Take item i
    )
    """
    print(f"\n🎒 0/1 Knapsack Problem")
    print(f"   Weights: {weights}")
    print(f"   Values: {values}")
    print(f"   Capacity: {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):
            # Don't take item i-1
            dp[i][w] = dp[i - 1][w]
            
            # Take item i-1 (if weight allows)
            if w >= weights[i - 1]:
                take_value = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], take_value)
    
    print(f"\n✓ Maximum value: {dp[n][capacity]}")
    return dp[n][capacity]

def knapsack_01_optimized(weights, values, capacity):
    """Space-optimized: Only need previous row"""
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # Traverse backwards to avoid overwriting needed values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

# ============================================================================
# UNBOUNDED KNAPSACK
# ============================================================================

def knapsack_unbounded(weights, values, capacity):
    """
    Unbounded Knapsack: Each item can be taken unlimited times
    
    dp[w] = maximum value with capacity w
    dp[w] = max(dp[w-weight[i]] + value[i]) for all items i
    """
    print(f"\n🎒 Unbounded Knapsack Problem")
    print(f"   Weights: {weights}")
    print(f"   Values: {values}")
    print(f"   Capacity: {capacity}")
    
    dp = [0] * (capacity + 1)
    
    for w in range(1, capacity + 1):
        for i in range(len(weights)):
            if w >= weights[i]:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    print(f"\n✓ Maximum value: {dp[capacity]}")
    return dp[capacity]

# ============================================================================
# SUBSET SUM
# ============================================================================

def subset_sum(nums, target):
    """
    Subset Sum: Can we form target sum using subset of nums?
    
    dp[i][s] = can we form sum s using first i numbers?
    dp[i][s] = dp[i-1][s] or dp[i-1][s-nums[i-1]]
    """
    print(f"\n✅ Subset Sum Problem")
    print(f"   Numbers: {nums}")
    print(f"   Target: {target}")
    
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    # Base case: sum 0 can always be formed (empty subset)
    for i in range(n + 1):
        dp[i][0] = True
    
    for i in range(1, n + 1):
        for s in range(1, target + 1):
            # Don't use nums[i-1]
            dp[i][s] = dp[i - 1][s]
            
            # Use nums[i-1]
            if s >= nums[i - 1]:
                dp[i][s] = dp[i][s] or dp[i - 1][s - nums[i - 1]]
    
    result = dp[n][target]
    print(f"\n✓ Can form target sum: {result}")
    return result

def subset_sum_optimized(nums, target):
    """Space-optimized subset sum"""
    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]

# ============================================================================
# PARTITION EQUAL SUBSET SUM
# ============================================================================

def can_partition(nums):
    """
    Partition Equal Subset Sum: Can partition array into two equal-sum subsets?
    This is subset sum with target = sum(nums) / 2
    """
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    return subset_sum_optimized(nums, target)

# ============================================================================
# COIN CHANGE (KNAPSACK VARIANT)
# ============================================================================

def coin_change_knapsack(coins, amount):
    """
    Coin Change as Unbounded Knapsack
    Each coin can be used unlimited times
    Minimize number of coins
    """
    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

# ============================================================================
# TARGET SUM
# ============================================================================

def target_sum(nums, target):
    """
    Target Sum: Assign + or - to each number to get target
    This reduces to subset sum problem
    """
    total = sum(nums)
    if (total + target) % 2 != 0 or total < abs(target):
        return 0
    
    # Find subset with sum = (total + target) / 2
    new_target = (total + target) // 2
    
    dp = [0] * (new_target + 1)
    dp[0] = 1
    
    for num in nums:
        for s in range(new_target, num - 1, -1):
            dp[s] += dp[s - num]
    
    return dp[new_target]

# ============================================================================
# EXAMPLE 1: 0/1 Knapsack
# ============================================================================

print("=" * 70)
print("Example 1: 0/1 Knapsack")
print("=" * 70)

weights1 = [1, 3, 4, 5]
values1 = [1, 4, 5, 7]
capacity1 = 7
knapsack_01(weights1, values1, capacity1)

# ============================================================================
# EXAMPLE 2: Unbounded Knapsack
# ============================================================================

print("\n" + "=" * 70)
print("Example 2: Unbounded Knapsack")
print("=" * 70)

weights2 = [1, 3, 4]
values2 = [10, 40, 50]
capacity2 = 8
knapsack_unbounded(weights2, values2, capacity2)

# ============================================================================
# EXAMPLE 3: Subset Sum
# ============================================================================

print("\n" + "=" * 70)
print("Example 3: Subset Sum")
print("=" * 70)

nums1 = [3, 34, 4, 12, 5, 2]
target1 = 9
subset_sum(nums1, target1)

# ============================================================================
# EXAMPLE 4: Partition Equal Subset Sum
# ============================================================================

print("\n" + "=" * 70)
print("Example 4: Partition Equal Subset Sum")
print("=" * 70)

nums2 = [1, 5, 11, 5]
print(f"   Numbers: {nums2}")
result = can_partition(nums2)
print(f"   Can partition equally: {result}")

# ============================================================================
# KNAPSACK PATTERNS
# ============================================================================

def knapsack_patterns():
    """
    Common knapsack problem patterns
    """
    print("\n" + "=" * 70)
    print("Knapsack Problem Patterns")
    print("=" * 70)
    
    print("\n📦 0/1 Knapsack:")
    print("   • Each item: take or don't take")
    print("   • dp[i][w] = max(don't take, take)")
    print("   • Loop backwards for space optimization")
    
    print("\n♾️ Unbounded Knapsack:")
    print("   • Items can be taken unlimited times")
    print("   • dp[w] = max over all items")
    print("   • Similar to coin change")
    
    print("\n✅ Subset Sum:")
    print("   • Boolean DP: can we form sum?")
    print("   • dp[i][s] = dp[i-1][s] OR dp[i-1][s-num]")
    
    print("\n💡 Key Insight:")
    print("   All knapsack problems share same structure:")
    print("   • State: capacity/weight constraint")
    print("   • Choice: include item or not")
    print("   • Transition: max/min over choices")

# ============================================================================
# COMPLEXITY ANALYSIS
# ============================================================================

print("\n" + "=" * 70)
print("Complexity Analysis")
print("=" * 70)

print(f"\n{'Problem':<30} {'Time':<25} {'Space'}")
print("─" * 75)
print(f"{'0/1 Knapsack':<30} {'O(n × capacity)':<25} {'O(n × capacity)'}")
print(f"{'0/1 (optimized)':<30} {'O(n × capacity)':<25} {'O(capacity)'}")
print(f"{'Unbounded Knapsack':<30} {'O(n × capacity)':<25} {'O(capacity)'}")
print(f"{'Subset Sum':<30} {'O(n × target)':<25} {'O(target)'}")

# ============================================================================
# KEY TAKEAWAYS
# ============================================================================

print("\n" + "=" * 70)
print("Key Takeaways")
print("=" * 70)

print("\n✓ Knapsack = optimization with constraints")
print("✓ 0/1: Each item once, 2D DP")
print("✓ Unbounded: Items unlimited, 1D DP")
print("✓ Subset Sum: Boolean DP, can we form sum?")
print("✓ Key pattern: dp[i][w] = max(include item, exclude item)")
print("✓ Space optimization: Loop backwards for 0/1 knapsack")
print("✓ Coin change is essentially unbounded knapsack")

knapsack_patterns()

Output

Click Run to execute your code

Pattern Summary

Key Patterns

1D DP: dp[i] = answer ending/up to index i. Common: max/min, sum, count
2D DP: dp[i][j] = answer at (i,j) or for sequences up to i and j. Common: paths, matching, optimization
Knapsack: dp[i][w] = best value with capacity w. Common: include/exclude choices

Complexity Analysis

Problem Type	Time	Space
1D DP	O(n)	O(n) or O(1)
2D DP	O(m × n)	O(m × n) or O(n)
Knapsack	O(n × W)	O(W)

Summary

What You've Learned

1D DP: Single array, linear problems (House Robber, Coin Change, LIS)
2D DP: Matrix, grid/sequence problems (LCS, Edit Distance, Unique Paths)
Knapsack: Selection with constraints (0/1, Unbounded, Subset Sum)
Space Optimization: Often can reduce from O(n²) to O(n) or O(1)
Pattern Recognition: Learn to identify which DP pattern fits a problem

What's Next?

You've mastered the core DP patterns! Next, we'll explore Advanced DP - DP on strings, trees, bitmask DP, and problem-solving strategies to tackle any DP challenge!

Previous DP Fundamentals

Next Advanced DP

Part 1: 1D DP Problems

House Robber Problem

Problem

Coin Change

Two Variants

Other 1D DP Problems

The Complete Code: 1D DP

Part 2: 2D DP Problems

Longest Common Subsequence (LCS)

Problem

Edit Distance (Levenshtein)

Problem

Unique Paths

The Complete Code: 2D DP

Part 3: Knapsack Problems

0/1 Knapsack

Problem

Unbounded Knapsack

Key Difference

Subset Sum

The Complete Code: Knapsack

Pattern Summary

Key Patterns

Complexity Analysis

Summary

What You've Learned

What's Next?

Enjoying these tutorials?