🚀 Advanced DP

Advanced ~50 min read

You've mastered the core DP patterns! Now let's tackle advanced topics: DP on strings (palindromes, word matching), DP on trees (path optimization), bitmask DP (TSP), and most importantly - how to recognize and solve any DP problem!

Part 1: DP on Strings

String DP problems often use 2D tables where dp[i][j] represents the answer for substring s[i:j] or sequences involving positions i and j.

Longest Palindromic Subsequence (LPS)

Problem

Find longest subsequence that is a palindrome.

State: dp[i][j] = LPS length of s[i:j+1]

Transition: 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])

Word Break

Problem

Can string be segmented into dictionary words?

State: dp[i] = can s[0:i] be segmented?

Application: Text processing, spell checkers, natural language processing

The Complete Code: DP on Strings

"""
DP on Strings
Palindrome problems, Word Break, and other string DP problems
"""

# ============================================================================
# LONGEST PALINDROMIC SUBSEQUENCE
# ============================================================================

def longest_palindromic_subsequence(s):
    """
    Longest Palindromic Subsequence (LPS)
    
    dp[i][j] = LPS length of s[i:j+1]
    dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j]
             = max(dp[i+1][j], dp[i][j-1]) otherwise
    """
    print(f"\n🔤 Longest Palindromic Subsequence")
    print(f"   String: {s}")
    
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single character is palindrome of length 1
    for i in range(n):
        dp[i][i] = 1
    
    # Fill for lengths 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]:
                if length == 2:
                    dp[i][j] = 2
                else:
                    dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    print(f"\n✓ LPS length: {dp[0][n - 1]}")
    return dp[0][n - 1]

# ============================================================================
# LONGEST PALINDROMIC SUBSTRING
# ============================================================================

def longest_palindromic_substring(s):
    """
    Longest Palindromic Substring (continuous)
    
    dp[i][j] = True if s[i:j+1] is palindrome
    dp[i][j] = True if s[i] == s[j] and dp[i+1][j-1]
    """
    print(f"\n🔤 Longest Palindromic Substring")
    print(f"   String: {s}")
    
    n = len(s)
    if not s:
        return ""
    
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    
    # Single character is palindrome
    for i in range(n):
        dp[i][i] = True
    
    # Check for length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2
    
    # Check for length 3 and more
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start = i
                max_len = length
    
    result = s[start:start + max_len]
    print(f"\n✓ Longest palindromic substring: '{result}' (length: {max_len})")
    return result

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

def min_palindrome_cuts(s):
    """
    Minimum cuts to partition string into palindromes
    """
    n = len(s)
    if not s:
        return 0
    
    # Precompute palindrome table
    is_palindrome = [[False] * n for _ in range(n)]
    
    # Single characters
    for i in range(n):
        is_palindrome[i][i] = True
    
    # Length 2
    for i in range(n - 1):
        is_palindrome[i][i + 1] = (s[i] == s[i + 1])
    
    # Length 3+
    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: minimum cuts
    dp = [0] * (n + 1)
    
    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)
    
    return dp[n]

# ============================================================================
# WORD BREAK
# ============================================================================

def word_break(s, word_dict):
    """
    Word Break: Can string be segmented into dictionary words?
    
    dp[i] = can s[0:i] be segmented?
    dp[i] = True if exists j < i such that dp[j] and s[j:i] in word_dict
    """
    print(f"\n📚 Word Break")
    print(f"   String: {s}")
    print(f"   Dictionary: {word_dict}")
    
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string can be segmented
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_dict:
                dp[i] = True
                break
    
    print(f"\n✓ Can be segmented: {dp[n]}")
    return dp[n]

def word_break_all(s, word_dict):
    """
    Word Break II: Return all possible sentences
    """
    def backtrack(start, memo):
        if start in memo:
            return memo[start]
        
        if start == len(s):
            return [""]
        
        result = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_dict:
                for sentence in backtrack(end, memo):
                    if sentence:
                        result.append(word + " " + sentence)
                    else:
                        result.append(word)
        
        memo[start] = result
        return result
    
    return backtrack(0, {})

# ============================================================================
# EDIT DISTANCE (STRING ALIGNMENT)
# ============================================================================

def edit_distance_detailed(word1, word2):
    """
    Edit Distance with operation tracking
    """
    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
    
    # 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
                )
    
    return dp[m][n]

# ============================================================================
# DISTINCT SUBSEQUENCES
# ============================================================================

def num_distinct_subsequences(s, t):
    """
    Distinct Subsequences: How many times t appears as subsequence in s?
    
    dp[i][j] = number of distinct subsequences of s[0:i] that equals t[0:j]
    """
    print(f"\n🔍 Distinct Subsequences")
    print(f"   String: {s}")
    print(f"   Pattern: {t}")
    
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Empty pattern matches empty string
    for i in range(m + 1):
        dp[i][0] = 1
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                # Match: can take (match) or skip (don't match)
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            else:
                # No match: must skip
                dp[i][j] = dp[i - 1][j]
    
    print(f"\n✓ Distinct subsequences: {dp[m][n]}")
    return dp[m][n]

# ============================================================================
# REGULAR EXPRESSION MATCHING
# ============================================================================

def is_match(s, p):
    """
    Regular Expression Matching: '.' matches any char, '*' matches zero or more of preceding
    
    dp[i][j] = does s[0:i] match p[0:j]?
    """
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # Empty string matches empty pattern
    dp[0][0] = True
    
    # Handle patterns like a*, a*b*, a*b*c*
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                # Zero occurrences
                dp[i][j] = dp[i][j - 2]
                # One or more occurrences
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
    
    return dp[m][n]

# ============================================================================
# EXAMPLE 1: Longest Palindromic Subsequence
# ============================================================================

print("=" * 70)
print("Example 1: Longest Palindromic Subsequence")
print("=" * 70)

s1 = "bbbab"
longest_palindromic_subsequence(s1)

# ============================================================================
# EXAMPLE 2: Longest Palindromic Substring
# ============================================================================

print("\n" + "=" * 70)
print("Example 2: Longest Palindromic Substring")
print("=" * 70)

s2 = "babad"
longest_palindromic_substring(s2)

# ============================================================================
# EXAMPLE 3: Word Break
# ============================================================================

print("\n" + "=" * 70)
print("Example 3: Word Break")
print("=" * 70)

s3 = "leetcode"
word_dict = {"leet", "code"}
word_break(s3, word_dict)

# ============================================================================
# EXAMPLE 4: Distinct Subsequences
# ============================================================================

print("\n" + "=" * 70)
print("Example 4: Distinct Subsequences")
print("=" * 70)

s4 = "rabbbit"
t4 = "rabbit"
num_distinct_subsequences(s4, t4)

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

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

print(f"\n{'Problem':<35} {'Time':<25} {'Space'}")
print("─" * 85)
print(f"{'LPS (Subsequence)':<35} {'O(n²)':<25} {'O(n²)'}")
print(f"{'LPS (Substring)':<35} {'O(n²)':<25} {'O(n²)'}")
print(f"{'Word Break':<35} {'O(n²)':<25} {'O(n)'}")
print(f"{'Edit Distance':<35} {'O(m × n)':<25} {'O(m × n)'}")
print(f"{'Distinct Subsequences':<35} {'O(m × n)':<25} {'O(m × n)'}")
print(f"{'Regex Matching':<35} {'O(m × n)':<25} {'O(m × n)'}")

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

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

print("\n✓ DP on strings often uses 2D table dp[i][j]")
print("✓ Common patterns: palindrome, matching, subsequence")
print("✓ LPS: dp[i][j] = dp[i+1][j-1] + 2 if match, else max of neighbors")
print("✓ Word Break: dp[i] = can segment s[0:i]?")
print("✓ Think: What does dp[i][j] represent for substring s[i:j]?")
print("✓ Many string DP problems are variations of LCS or edit distance")

Output

Click Run to execute your code

Part 2: DP on Trees

Tree DP uses post-order DFS where we process children first, then compute current node's value based on children.

Maximum Path Sum

Problem

Find maximum sum path in binary tree (any node to any node).

Key Insight: For each node, compute max path through it and max path extending upward

Return value: Max path from node downward (can extend to parent)

Global max: Track max path sum across all nodes

Diameter of Binary Tree

Problem

Longest path between any two nodes (number of edges).

Approach: For each node, diameter = left_depth + right_depth

Return value: Max depth from node

House Robber III

Rob houses arranged in tree. Can't rob connected nodes. Returns [rob_this_node, skip_this_node] state.

The Complete Code: DP on Trees

"""
DP on Trees
Max Path Sum, Diameter, House Robber III, and other tree DP problems
"""

class TreeNode:
    """Binary Tree Node"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# ============================================================================
# MAXIMUM PATH SUM (BINARY TREE)
# ============================================================================

def max_path_sum(root):
    """
    Maximum Path Sum: Maximum sum path in binary tree (any node to any node)
    
    Returns maximum path sum
    Uses post-order traversal with DP
    """
    max_sum = [float('-inf')]  # Use list to pass by reference
    
    def dfs(node):
        if not node:
            return 0
        
        # Get max path from left and right subtrees
        left_sum = max(0, dfs(node.left))   # Ignore negative sums
        right_sum = max(0, dfs(node.right))
        
        # Current path sum: node + left + right
        current_sum = node.val + left_sum + right_sum
        max_sum[0] = max(max_sum[0], current_sum)
        
        # Return max path that can be extended to parent
        return node.val + max(left_sum, right_sum)
    
    dfs(root)
    return max_sum[0]

# ============================================================================
# DIAMETER OF BINARY TREE
# ============================================================================

def diameter_of_binary_tree(root):
    """
    Diameter: Longest path between any two nodes (number of edges)
    
    For each node, diameter = max depth of left + max depth of right
    """
    max_diameter = [0]
    
    def dfs(node):
        if not node:
            return 0
        
        left_depth = dfs(node.left)
        right_depth = dfs(node.right)
        
        # Diameter passing through this node
        current_diameter = left_depth + right_depth
        max_diameter[0] = max(max_diameter[0], current_diameter)
        
        # Return max depth from this node
        return max(left_depth, right_depth) + 1
    
    dfs(root)
    return max_diameter[0]

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

def house_robber_iii(root):
    """
    House Robber III: Binary tree of houses, can't rob connected nodes
    
    Returns [rob_this_node, skip_this_node]
    """
    def dfs(node):
        if not node:
            return [0, 0]  # [rob, skip]
        
        left = dfs(node.left)
        right = dfs(node.right)
        
        # Rob this node: must skip children
        rob = node.val + left[1] + right[1]
        
        # Skip this node: can choose best from children
        skip = max(left) + max(right)
        
        return [rob, skip]
    
    result = dfs(root)
    return max(result)

# ============================================================================
# BINARY TREE MAXIMUM PATH SUM (ALGORITHM EXPLANATION)
# ============================================================================

def max_path_sum_explained(root):
    """
    Detailed explanation of max path sum algorithm
    """
    print(f"\n🌳 Maximum Path Sum in Binary Tree")
    
    max_sum = [float('-inf')]
    
    def dfs(node, path=""):
        if not node:
            return 0
        
        current_path = f"{path} -> {node.val}" if path else str(node.val)
        print(f"   Visiting node: {node.val} (path: {current_path})")
        
        left_sum = max(0, dfs(node.left, current_path))
        right_sum = max(0, dfs(node.right, current_path))
        
        print(f"   Node {node.val}: left_sum={left_sum}, right_sum={right_sum}")
        
        current_sum = node.val + left_sum + right_sum
        max_sum[0] = max(max_sum[0], current_sum)
        print(f"   Current path sum through {node.val}: {current_sum}")
        print(f"   Global max so far: {max_sum[0]}")
        
        return_val = node.val + max(left_sum, right_sum)
        print(f"   Returning to parent: {return_val} (can extend this path)")
        return return_val
    
    dfs(root)
    print(f"\n✓ Maximum path sum: {max_sum[0]}")
    return max_sum[0]

# ============================================================================
# LONGEST PATH IN TREE
# ============================================================================

def longest_path_in_tree(root):
    """
    Longest path (not necessarily diameter) in tree
    Similar to diameter but with different constraint
    """
    max_path = [0]
    
    def dfs(node):
        if not node:
            return 0
        
        left = dfs(node.left)
        right = dfs(node.right)
        
        # Longest path through this node
        through_node = left + right + 1
        max_path[0] = max(max_path[0], through_node)
        
        # Return longest path from this node downward
        return max(left, right) + 1
    
    dfs(root)
    return max_path[0] - 1  # Subtract 1 to get number of edges

# ============================================================================
# SUM OF ALL LEFT LEAVES
# ============================================================================

def sum_of_left_leaves(root):
    """
    Sum of all left leaves in binary tree
    DP-style: track if node is left child
    """
    total = [0]
    
    def dfs(node, is_left=False):
        if not node:
            return
        
        if not node.left and not node.right and is_left:
            total[0] += node.val
        
        dfs(node.left, True)
        dfs(node.right, False)
    
    dfs(root)
    return total[0]

# ============================================================================
# MAXIMUM AVERAGE SUBTREE
# ============================================================================

def maximum_average_subtree(root):
    """
    Maximum average value in any subtree
    Returns max average
    """
    max_avg = [float('-inf')]
    
    def dfs(node):
        if not node:
            return [0, 0]  # [sum, count]
        
        left = dfs(node.left)
        right = dfs(node.right)
        
        total_sum = node.val + left[0] + right[0]
        total_count = 1 + left[1] + right[1]
        
        avg = total_sum / total_count
        max_avg[0] = max(max_avg[0], avg)
        
        return [total_sum, total_count]
    
    dfs(root)
    return max_avg[0]

# ============================================================================
# TREE DP PATTERNS
# ============================================================================

def tree_dp_patterns():
    """
    Common patterns for DP on trees
    """
    print("\n" + "=" * 70)
    print("Tree DP Patterns")
    print("=" * 70)
    
    print("\n🌳 Key Insight:")
    print("   Tree DP uses DFS (post-order traversal)")
    print("   Process children first, then current node")
    
    print("\n📋 Common Patterns:")
    print("   1. Bottom-up: Return value from children, compute current")
    print("   2. Pass-by-reference: Use list/array for global maximum")
    print("   3. Two states: Often return [with_node, without_node]")
    
    print("\n🔑 State Definition:")
    print("   • Return value: Best path/sum from this node downward")
    print("   • Global variable: Best overall answer across all nodes")
    
    print("\n💡 Example Pattern:")
    print("   def dfs(node):")
    print("       if not node: return 0")
    print("       left = dfs(node.left)")
    print("       right = dfs(node.right)")
    print("       current = compute(node, left, right)")
    print("       global_max = max(global_max, current)")
    print("       return extend_to_parent(node, left, right)")

# ============================================================================
# EXAMPLE 1: Maximum Path Sum
# ============================================================================

print("=" * 70)
print("Example 1: Maximum Path Sum")
print("=" * 70)

# Create example tree: [-10, 9, 20, null, null, 15, 7]
root1 = TreeNode(-10)
root1.left = TreeNode(9)
root1.right = TreeNode(20)
root1.right.left = TreeNode(15)
root1.right.right = TreeNode(7)

print(f"   Tree structure:")
print(f"        -10")
print(f"       /  \\")
print(f"      9    20")
print(f"          /  \\")
print(f"         15   7")

result1 = max_path_sum(root1)
print(f"\n✓ Maximum path sum: {result1}")

# ============================================================================
# EXAMPLE 2: Diameter of Binary Tree
# ============================================================================

print("\n" + "=" * 70)
print("Example 2: Diameter of Binary Tree")
print("=" * 70)

# Create example tree: [1, 2, 3, 4, 5]
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(3)
root2.left.left = TreeNode(4)
root2.left.right = TreeNode(5)

diameter = diameter_of_binary_tree(root2)
print(f"\n✓ Diameter: {diameter} edges")

# ============================================================================
# EXAMPLE 3: House Robber III
# ============================================================================

print("\n" + "=" * 70)
print("Example 3: House Robber III")
print("=" * 70)

# Create example tree: [3, 2, 3, null, 3, null, 1]
root3 = TreeNode(3)
root3.left = TreeNode(2)
root3.right = TreeNode(3)
root3.left.right = TreeNode(3)
root3.right.right = TreeNode(1)

max_rob = house_robber_iii(root3)
print(f"\n✓ Maximum money robbed: {max_rob}")

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

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

print(f"\n{'Problem':<35} {'Time':<25} {'Space'}")
print("─" * 85)
print(f"{'Max Path Sum':<35} {'O(n)':<25} {'O(h)'}")
print(f"{'Diameter':<35} {'O(n)':<25} {'O(h)'}")
print(f"{'House Robber III':<35} {'O(n)':<25} {'O(h)'}")
print(f"\n   n = number of nodes, h = height of tree (O(log n) balanced, O(n) worst)")

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

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

print("\n✓ Tree DP uses post-order DFS (children first)")
print("✓ Return value: best path/value from node downward")
print("✓ Global variable: best overall answer")
print("✓ Common pattern: process children, compute current, update global")
print("✓ Max Path Sum: node + left + right, return node + max(left, right)")
print("✓ Diameter: left_depth + right_depth, return max_depth + 1")
print("✓ House Robber III: [rob_node, skip_node] state")

tree_dp_patterns()

Output

Click Run to execute your code

Part 3: Advanced DP Patterns

Advanced patterns use clever state compression and optimization techniques.

Bitmask DP

Traveling Salesman Problem (TSP)

Visit all cities exactly once with minimum cost. Uses bitmask to represent visited cities.

State: dp[mask][last] = min cost to visit cities in mask, ending at last

Application: Route optimization, task scheduling, assignment problems

Complexity: O(2^n × n²) - exponential but efficient for n ≤ 20

Digit DP

Problem

Count numbers with constraints (e.g., no consecutive digits, sum constraints).

Approach: Process digits one by one, track state (tight bound, previous digit, etc.)

State Compression

Reduce state space using clever encoding. Common in optimization problems.

The Complete Code: Advanced DP Patterns

"""
Advanced DP Patterns
Bitmask DP, Digit DP, State Compression
"""

# ============================================================================
# TRAVELING SALESMAN PROBLEM (TSP) WITH BITMASK
# ============================================================================

def tsp_bitmask(distances):
    """
    TSP using Bitmask DP
    distances[i][j] = distance from city i to city j
    
    dp[mask][last] = minimum cost to visit all cities in mask, ending at last
    mask: bitmask representing visited cities
    """
    print(f"\n🗺️ Traveling Salesman Problem (Bitmask DP)")
    print(f"   Cities: {len(distances)}")
    
    n = len(distances)
    # dp[mask][last] = minimum cost
    dp = [[float('inf')] * n for _ in range(1 << n)]
    
    # Base case: starting from city 0
    dp[1][0] = 0  # mask = 1 means only city 0 visited
    
    # Try all masks
    for mask in range(1, 1 << n):
        for last in range(n):
            if not (mask & (1 << last)):
                continue  # last city not in mask
            
            # Try extending path
            for next_city in range(n):
                if mask & (1 << next_city):
                    continue  # Already visited
                
                new_mask = mask | (1 << next_city)
                dp[new_mask][next_city] = min(
                    dp[new_mask][next_city],
                    dp[mask][last] + distances[last][next_city]
                )
    
    # Return to starting city
    final_mask = (1 << n) - 1  # All cities visited
    result = float('inf')
    for last in range(n):
        result = min(result, dp[final_mask][last] + distances[last][0])
    
    print(f"\n✓ Minimum TSP cost: {result}")
    return result

# ============================================================================
# ASSIGNMENT PROBLEM WITH BITMASK
# ============================================================================

def assignment_problem_bitmask(cost_matrix):
    """
    Assignment Problem: Assign n tasks to n workers with minimum cost
    Uses bitmask to represent assigned tasks
    """
    print(f"\n👥 Assignment Problem (Bitmask DP)")
    print(f"   Workers: {len(cost_matrix)}, Tasks: {len(cost_matrix[0])}")
    
    n = len(cost_matrix)
    # dp[mask] = minimum cost to assign tasks in mask
    dp = [float('inf')] * (1 << n)
    dp[0] = 0  # No tasks assigned
    
    for mask in range(1 << n):
        # Count assigned tasks
        assigned = bin(mask).count('1')
        
        if assigned >= n:
            continue
        
        # Try assigning next task to worker 'assigned'
        for task in range(n):
            if mask & (1 << task):
                continue  # Task already assigned
            
            new_mask = mask | (1 << task)
            dp[new_mask] = min(dp[new_mask], dp[mask] + cost_matrix[assigned][task])
    
    result = dp[(1 << n) - 1]
    print(f"\n✓ Minimum assignment cost: {result}")
    return result

# ============================================================================
# DIGIT DP: COUNT NUMBERS WITH CONSTRAINTS
# ============================================================================

def count_numbers_with_constraint(n, condition):
    """
    Digit DP: Count numbers from 0 to n that satisfy condition
    Example: Count numbers with no consecutive digits
    """
    s = str(n)
    digits = [int(c) for c in s]
    
    def dfs(pos, tight, prev, memo):
        """
        pos: current position
        tight: whether previous digits match n
        prev: previous digit
        memo: memoization
        """
        if pos == len(digits):
            return 1
        
        key = (pos, tight, prev)
        if key in memo:
            return memo[key]
        
        limit = digits[pos] if tight else 9
        count = 0
        
        for d in range(limit + 1):
            new_tight = tight and (d == limit)
            # Condition: no consecutive same digits
            if d != prev:
                count += dfs(pos + 1, new_tight, d, memo)
        
        memo[key] = count
        return count
    
    return dfs(0, True, -1, {})

# ============================================================================
# STATE COMPRESSION: PROFIT SCHEDULING
# ============================================================================

def max_profit_scheduling(startTime, endTime, profit):
    """
    Job Scheduling with State Compression
    Maximize profit by scheduling non-overlapping jobs
    """
    print(f"\n📅 Job Scheduling (State Compression)")
    
    n = len(startTime)
    jobs = sorted(zip(endTime, startTime, profit))
    
    # dp[i] = maximum profit using first i jobs
    dp = [0] * (n + 1)
    
    for i in range(1, n + 1):
        end, start, prof = jobs[i - 1]
        
        # Don't take job i
        dp[i] = dp[i - 1]
        
        # Take job i - find last compatible job
        # Binary search for last job ending <= start
        left, right = 0, i - 1
        last_compatible = -1
        
        while left <= right:
            mid = (left + right) // 2
            if jobs[mid][0] <= start:
                last_compatible = mid
                left = mid + 1
            else:
                right = mid - 1
        
        if last_compatible != -1:
            dp[i] = max(dp[i], dp[last_compatible + 1] + prof)
        else:
            dp[i] = max(dp[i], prof)
    
    print(f"\n✓ Maximum profit: {dp[n]}")
    return dp[n]

# ============================================================================
# BITMASK SUBSET DP
# ============================================================================

def bitmask_subset_dp_example(n):
    """
    Example: Count all subsets that sum to target using bitmask
    """
    print(f"\n🔢 Bitmask Subset DP Example")
    print(f"   Total subsets of {n} elements: {2**n}")
    
    count = 0
    for mask in range(1 << n):
        # Process subset represented by mask
        subset = [i for i in range(n) if mask & (1 << i)]
        count += 1
    
    print(f"   Total subsets: {count}")
    return count

# ============================================================================
# PALINDROME PARTITIONING (BITMASK APPROACH)
# ============================================================================

def palindrome_partitioning_bitmask(s):
    """
    Minimum palindrome partitioning using bitmask
    """
    n = len(s)
    if not s:
        return 0
    
    # Precompute palindromes
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n - 1):
        is_pal[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_pal[i][j] = (s[i] == s[j] and is_pal[i + 1][j - 1])
    
    # Bitmask DP
    dp = [float('inf')] * (1 << n)
    dp[0] = 0
    
    for mask in range(1, 1 << n):
        # Find last set bit
        last = mask.bit_length() - 1
        
        # Try all possible endings
        for end in range(last + 1):
            if not (mask & (1 << end)):
                continue
            
            # Check if substring is palindrome
            start = 0
            for i in range(end + 1):
                if mask & (1 << i):
                    start = i
                    break
            
            if is_pal[start][end]:
                prev_mask = mask & ~((1 << (end + 1)) - 1) | ((1 << start) - 1)
                dp[mask] = min(dp[mask], dp[prev_mask] + 1)
    
    return dp[(1 << n) - 1]

# ============================================================================
# BITMASK DP PATTERNS
# ============================================================================

def bitmask_dp_patterns():
    """
    Common patterns for Bitmask DP
    """
    print("\n" + "=" * 70)
    print("Bitmask DP Patterns")
    print("=" * 70)
    
    print("\n🔑 Key Concepts:")
    print("   • Bitmask: Integer representing set (1 = included, 0 = excluded)")
    print("   • mask & (1 << i): Check if element i is in set")
    print("   • mask | (1 << i): Add element i to set")
    print("   • mask ^ (1 << i): Toggle element i in set")
    print("   • (1 << n) - 1: All n elements included")
    
    print("\n📋 Common Problems:")
    print("   1. TSP: Visit all cities exactly once")
    print("   2. Assignment: Assign tasks to workers")
    print("   3. Subset DP: Optimize over all subsets")
    print("   4. State Compression: Reduce state space")
    
    print("\n💡 State Definition:")
    print("   dp[mask][additional_state] = answer for subset mask")
    print("   Example: dp[mask][last] = min cost to visit mask, ending at last")

# ============================================================================
# EXAMPLE 1: TSP with Bitmask
# ============================================================================

print("=" * 70)
print("Example 1: Traveling Salesman Problem")
print("=" * 70)

# Example: 4 cities
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

tsp_bitmask(distances)

# ============================================================================
# EXAMPLE 2: Assignment Problem
# ============================================================================

print("\n" + "=" * 70)
print("Example 2: Assignment Problem")
print("=" * 70)

cost_matrix = [
    [9, 2, 7, 8],
    [6, 4, 3, 7],
    [5, 8, 1, 8],
    [7, 6, 9, 4]
]

assignment_problem_bitmask(cost_matrix)

# ============================================================================
# EXAMPLE 3: Bitmask Subset DP
# ============================================================================

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

bitmask_subset_dp_example(4)

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

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

print(f"\n{'Problem':<35} {'Time':<30} {'Space'}")
print("─" * 95)
print(f"{'TSP (Bitmask)':<35} {'O(2^n × n²)':<30} {'O(2^n × n)'}")
print(f"{'Assignment (Bitmask)':<35} {'O(2^n × n)':<30} {'O(2^n)'}")
print(f"{'Digit DP':<35} {'O(log n × states)':<30} {'O(log n × states)'}")
print(f"\n   Note: Bitmask DP is exponential in n, but efficient for n ≤ 20")

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

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

print("\n✓ Bitmask DP: Use integers to represent sets")
print("✓ Efficient for small sets (typically n ≤ 20)")
print("✓ State: dp[mask] or dp[mask][additional_state]")
print("✓ TSP: Classic bitmask DP problem")
print("✓ Digit DP: Process digits one by one with constraints")
print("✓ State Compression: Reduce state space using clever encoding")

bitmask_dp_patterns()

Output

Click Run to execute your code

Part 4: DP Problem-Solving Strategy

Learn how to recognize DP problems and develop a systematic approach to solve them.

How to Recognize DP Problems

Key Indicators

Optimization Problem: Min, max, count possibilities
Overlapping Subproblems: Same problem solved multiple times
Optimal Substructure: Optimal solution contains optimal subproblems
Can Break into Subproblems: Problem naturally divides

DP Problem-Solving Steps

Systematic Approach

Understand: Read problem carefully, identify what to optimize
Identify Subproblems: What are smaller versions?
Define State: What does dp[i] or dp[i][j] represent?
Find Recurrence: How to compute dp[i] from previous states?
Set Base Cases: Smallest subproblems (no dependencies)
Choose Implementation: Memoization (top-down) or Tabulation (bottom-up)
Optimize Space: Can we reduce space complexity?

Common DP Patterns

Pattern	State	Transition	Examples
Linear	dp[i]	dp[i] = f(dp[i-1], dp[i-2])	Fibonacci, Climbing Stairs
Grid	dp[i][j]	dp[i][j] = f(dp[i-1][j], dp[i][j-1])	Unique Paths, Min Path Sum
Subsequence	dp[i][j]	Match or skip pattern	LCS, LIS
Knapsack	dp[i][w]	Include or exclude	0/1 Knapsack, Coin Change
Tree	Return value	Post-order DFS	Max Path Sum, Diameter
Bitmask	dp[mask]	Extend mask	TSP, Assignment

The Complete Code: DP Problem-Solving

"""
DP Problem-Solving Guide
How to recognize DP, common patterns, and strategy guide
"""

# ============================================================================
# HOW TO RECOGNIZE DP PROBLEMS
# ============================================================================

def how_to_recognize_dp():
    """
    Guide to recognizing DP problems
    """
    print("=" * 70)
    print("How to Recognize DP Problems")
    print("=" * 70)
    
    print("\n🔍 Key Indicators:")
    print("   1. Optimization Problem (min, max, count)")
    print("   2. Overlapping Subproblems (same problem solved multiple times)")
    print("   3. Optimal Substructure (optimal solution contains optimal subproblems)")
    print("   4. Can be broken into smaller subproblems")
    
    print("\n📝 Common Problem Types:")
    print("   • Maximize/Minimize value (profit, cost, path sum)")
    print("   • Count possibilities (ways, paths, combinations)")
    print("   • Decision problems (can we form? is it possible?)")
    print("   • Path/Movement problems (grid, graph traversal)")
    print("   • Sequence problems (arrays, strings)")
    
    print("\n❓ Questions to Ask:")
    print("   • Can I solve smaller version of this problem?")
    print("   • Does the answer for bigger problem depend on smaller ones?")
    print("   • Am I recomputing the same subproblem multiple times?")
    print("   • Is there a recurrence relation I can write?")

# ============================================================================
# COMMON DP PATTERNS
# ============================================================================

def common_dp_patterns():
    """
    Summary of common DP patterns
    """
    print("\n" + "=" * 70)
    print("Common DP Patterns")
    print("=" * 70)
    
    patterns = [
        {
            "name": "1D DP - Linear",
            "examples": ["Fibonacci", "Climbing Stairs", "House Robber"],
            "state": "dp[i] = answer for first i elements",
            "transition": "dp[i] = f(dp[i-1], dp[i-2], ...)"
        },
        {
            "name": "1D DP - Array/Sequence",
            "examples": ["LIS", "Coin Change", "Decode Ways"],
            "state": "dp[i] = answer ending/at index i",
            "transition": "dp[i] = f(dp[j]) for j < i"
        },
        {
            "name": "2D DP - Grid/Matrix",
            "examples": ["Unique Paths", "Min Path Sum", "Max Square"],
            "state": "dp[i][j] = answer at position (i, j)",
            "transition": "dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...)"
        },
        {
            "name": "2D DP - Two Sequences",
            "examples": ["LCS", "Edit Distance", "Interleaving String"],
            "state": "dp[i][j] = answer for first i of seq1, first j of seq2",
            "transition": "dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])"
        },
        {
            "name": "Knapsack",
            "examples": ["0/1 Knapsack", "Unbounded Knapsack", "Subset Sum"],
            "state": "dp[i][w] = answer using first i items with capacity w",
            "transition": "dp[i][w] = max(include, exclude)"
        },
        {
            "name": "Interval DP",
            "examples": ["Matrix Chain", "Palindrome Partitioning"],
            "state": "dp[i][j] = answer for interval [i, j]",
            "transition": "dp[i][j] = f(dp[i][k], dp[k+1][j]) for k in [i, j)"
        },
        {
            "name": "Tree DP",
            "examples": ["Max Path Sum", "Diameter", "House Robber III"],
            "state": "Return value from subtree, global max",
            "transition": "Post-order DFS, combine children"
        },
        {
            "name": "Bitmask DP",
            "examples": ["TSP", "Assignment Problem"],
            "state": "dp[mask] = answer for subset mask",
            "transition": "dp[mask] = f(dp[mask'], ...)"
        }
    ]
    
    for i, pattern in enumerate(patterns, 1):
        print(f"\n{i}. {pattern['name']}")
        print(f"   Examples: {', '.join(pattern['examples'])}")
        print(f"   State: {pattern['state']}")
        print(f"   Transition: {pattern['transition']}")

# ============================================================================
# DP SOLVING STRATEGY
# ============================================================================

def dp_solving_strategy():
    """
    Step-by-step strategy for solving DP problems
    """
    print("\n" + "=" * 70)
    print("DP Solving Strategy (Step-by-Step)")
    print("=" * 70)
    
    steps = [
        {
            "step": 1,
            "title": "Understand the Problem",
            "actions": [
                "Read problem carefully",
                "Identify what to optimize (max, min, count)",
                "Understand constraints"
            ]
        },
        {
            "step": 2,
            "title": "Identify Subproblems",
            "actions": [
                "What are the smaller versions?",
                "What does answer depend on?",
                "Think recursively: How to solve using subproblems?"
            ]
        },
        {
            "step": 3,
            "title": "Define State",
            "actions": [
                "dp[i] or dp[i][j] = what?",
                "State should capture necessary information",
                "Choose minimal state space"
            ]
        },
        {
            "step": 4,
            "title": "Find Recurrence Relation",
            "actions": [
                "How to compute dp[i] from previous states?",
                "Write formula: dp[i] = f(dp[...])",
                "Consider all choices/transitions"
            ]
        },
        {
            "step": 5,
            "title": "Identify Base Cases",
            "actions": [
                "Smallest subproblems (no dependencies)",
                "Edge cases (empty, single element, etc.)",
                "Set initial values"
            ]
        },
        {
            "step": 6,
            "title": "Choose Implementation",
            "actions": [
                "Memoization (top-down): Natural recursion",
                "Tabulation (bottom-up): Iterative, avoid stack",
                "Space optimization if possible"
            ]
        },
        {
            "step": 7,
            "title": "Code and Test",
            "actions": [
                "Implement solution",
                "Test with examples",
                "Check edge cases",
                "Verify time/space complexity"
            ]
        }
    ]
    
    for step_info in steps:
        print(f"\n{step_info['step']}. {step_info['title']}")
        for action in step_info['actions']:
            print(f"   • {action}")

# ============================================================================
# COMMON MISTAKES TO AVOID
# ============================================================================

def common_mistakes():
    """
    Common mistakes in DP problems
    """
    print("\n" + "=" * 70)
    print("Common Mistakes to Avoid")
    print("=" * 70)
    
    mistakes = [
        "Not identifying overlapping subproblems",
        "Wrong state definition (too much or too little information)",
        "Incorrect recurrence relation (missing cases)",
        "Forgetting base cases",
        "Off-by-one errors in indices",
        "Not handling edge cases (empty, single element)",
        "Using wrong data structure (should use array, not dict for tabulation)",
        "Not optimizing space when possible",
        "Confusing memoization and tabulation",
        "Not considering all transitions/choices"
    ]
    
    for i, mistake in enumerate(mistakes, 1):
        print(f"   {i}. {mistake}")

# ============================================================================
# PRACTICE RECOMMENDATIONS
# ============================================================================

def practice_recommendations():
    """
    Recommendations for practicing DP
    """
    print("\n" + "=" * 70)
    print("Practice Recommendations")
    print("=" * 70)
    
    print("\n📚 Start with Basics:")
    print("   1. Fibonacci variations (Climbing Stairs, etc.)")
    print("   2. Simple 1D DP (House Robber, Coin Change)")
    print("   3. Grid problems (Unique Paths)")
    
    print("\n📈 Progress to Intermediate:")
    print("   1. 2D DP (LCS, Edit Distance)")
    print("   2. Knapsack problems")
    print("   3. String DP (Palindrome, Word Break)")
    
    print("\n🚀 Advanced Topics:")
    print("   1. Interval DP")
    print("   2. Tree DP")
    print("   3. Bitmask DP")
    
    print("\n💡 Practice Strategy:")
    print("   • Solve same problem multiple ways (memoization vs tabulation)")
    print("   • Try to optimize space complexity")
    print("   • Draw DP tables for 2D problems")
    print("   • Trace through examples manually")
    print("   • Focus on pattern recognition")

# ============================================================================
# DP TEMPLATE
# ============================================================================

def dp_template():
    """
    Generic DP template
    """
    print("\n" + "=" * 70)
    print("Generic DP Template")
    print("=" * 70)
    
    print("\n# Memoization (Top-Down)")
    print("""
def solve(n, memo={}):
    # Base cases
    if n in memo:
        return memo[n]
    if base_case(n):
        return base_value
    
    # Recurrence relation
    result = combine(solve(subproblem1), solve(subproblem2), ...)
    memo[n] = result
    return result
""")
    
    print("\n# Tabulation (Bottom-Up)")
    print("""
def solve(n):
    # Initialize DP array
    dp = [0] * (n + 1)
    
    # Base cases
    dp[0] = base_value0
    dp[1] = base_value1
    
    # Fill DP table
    for i in range(2, n + 1):
        dp[i] = combine(dp[i-1], dp[i-2], ...)
    
    return dp[n]
""")

# ============================================================================
# MAIN SUMMARY
# ============================================================================

def main():
    """Main summary function"""
    how_to_recognize_dp()
    common_dp_patterns()
    dp_solving_strategy()
    common_mistakes()
    practice_recommendations()
    dp_template()
    
    print("\n" + "=" * 70)
    print("Final Thoughts")
    print("=" * 70)
    print("\n💡 DP is a powerful technique for optimization problems")
    print("💡 Key: Identify subproblems and recurrence relation")
    print("💡 Practice pattern recognition")
    print("💡 Start simple, build up complexity")
    print("💡 Draw tables, trace examples")
    print("\n🎯 Remember: DP = Optimal Substructure + Overlapping Subproblems")

if __name__ == "__main__":
    main()

Output

Click Run to execute your code

Summary

What You've Learned

String DP: 2D table for substrings, common in text processing
Tree DP: Post-order DFS, return values from children
Bitmask DP: Use integers as sets, efficient for small n
Problem-Solving: Systematic approach to recognize and solve DP problems
Pattern Recognition: Identify which DP pattern fits a problem
Space Optimization: Often can reduce space complexity significantly

Congratulations! 🎉

You've Completed Dynamic Programming!

You now understand:

✅ DP fundamentals (memoization vs tabulation)
✅ 1D, 2D, and Knapsack DP problems
✅ Advanced DP on strings and trees
✅ Bitmask DP and state compression
✅ Systematic problem-solving approach

This completes the Dynamic Programming module and brings you closer to mastering all DSA topics!

Previous DP Problems

Next DSA Home

Part 1: DP on Strings

Longest Palindromic Subsequence (LPS)

Problem

Word Break

Problem

Other String DP Problems

The Complete Code: DP on Strings

Part 2: DP on Trees

Maximum Path Sum

Problem

Diameter of Binary Tree

Problem

House Robber III

The Complete Code: DP on Trees

Part 3: Advanced DP Patterns

Bitmask DP

Traveling Salesman Problem (TSP)

Digit DP

Problem

State Compression

The Complete Code: Advanced DP Patterns

Part 4: DP Problem-Solving Strategy

How to Recognize DP Problems

Key Indicators

DP Problem-Solving Steps

Systematic Approach

Common DP Patterns

The Complete Code: DP Problem-Solving

Summary

What You've Learned

Congratulations! 🎉

You've Completed Dynamic Programming!

Enjoying these tutorials?