Learning Paths/Interview Mastery/Hard Dynamic Programming

Hard Dynamic Programming

Master advanced dynamic programming techniques to solve the most challenging algorithmic problems. This module covers complex DP patterns, optimization techniques, and strategies for tackling hard interview questions.

Module Contents

Learning Resources

Introduction to Hard Dynamic Programming

Dynamic Programming (DP) is a powerful technique for solving optimization problems by breaking them down into simpler subproblems. Hard DP problems typically involve complex state representations, multiple dimensions, or non-obvious recurrence relations.

Key Characteristics of Hard DP Problems

Complex State Representation: Requires multiple parameters to define a state
Non-Obvious Subproblems: The division into subproblems is not straightforward
Multiple Recurrence Relations: Different cases need different formulations
Optimization Constraints: Additional constraints that complicate the solution
High Dimensionality: States with 3+ dimensions
Large State Space: Requires optimization techniques to handle memory constraints

Advanced DP Patterns

Common Advanced Patterns:

State Compression DP: Using bit manipulation to represent states compactly
Interval DP: Solving problems on intervals or subarrays
Tree DP: Dynamic programming on tree structures
Digit DP: Counting numbers with specific digit properties
DP with Probability: Combining DP with probability calculations
DP on Graphs: Applying DP techniques to graph problems
Knuth's Optimization: Optimizing certain types of DP recurrences
Convex Hull Optimization: Optimizing DP with convex properties

Approaching Hard DP Problems

Systematic Approach:

Define the State: Clearly identify what each state represents
Identify Base Cases: Determine the simplest subproblems
Formulate Recurrence Relations: Express how states relate to each other
Determine Computation Order: Decide the order to fill the DP table
Implement Memoization or Tabulation: Choose the appropriate implementation approach
Optimize if Necessary: Apply space or time optimizations
Extract the Final Answer: Identify which state contains the solution

State Compression DP

State Compression DP uses bit manipulation to represent states compactly, allowing us to solve problems with large state spaces efficiently. This technique is particularly useful for problems involving subsets or permutations.

1. Traveling Salesman Problem (TSP)

The classic TSP problem asks for the shortest possible route that visits each city exactly once and returns to the origin city.

DP Formulation:

State: dp[mask][i] = minimum distance to visit all cities in the mask and end at city i
Mask: A bit mask where the j-th bit is 1 if city j has been visited
Recurrence Relation: dp[mask][i] = min(dp[mask ^ (1 << i)][j] + distance[j][i]) for all j in mask
Base Case: dp[1 << start][start] = 0 (starting at the start city)
Final Answer: dp[(1 << n) - 1][start] (all cities visited, ending at start)

// Traveling Salesman Problem using State Compression DP
int tsp(int[][] dist, int n, int start) {
    // dp[mask][i] = min cost to visit all cities in mask and end at city i
    int[][] dp = new int[1 << n][n];
    
    // Initialize dp array with infinity
    for (int i = 0; i < (1 << n); i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE / 2); // Avoid overflow
    }
    
    // Base case: start at the starting city
    dp[1 << start][start] = 0;
    
    // Fill dp table
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int end = 0; end < n; end++) {
            // Skip if end city is not in the current subset
            if ((mask & (1 << end)) == 0) continue;
            
            // Skip invalid states
            if (dp[mask][end] == Integer.MAX_VALUE / 2) continue;
            
            // Try to add a new city
            for (int next = 0; next < n; next++) {
                // Skip if next city is already visited
                if ((mask & (1 << next)) != 0) continue;
                
                // Calculate new mask with next city added
                int newMask = mask | (1 << next);
                
                // Update dp value
                dp[newMask][next] = Math.min(
                    dp[newMask][next],
                    dp[mask][end] + dist[end][next]
                );
            }
        }
    }
    
    // Find minimum cost to visit all cities and return to start
    int finalMask = (1 << n) - 1; // All cities visited
    int minCost = Integer.MAX_VALUE;
    
    for (int end = 0; end < n; end++) {
        if (end != start) {
            minCost = Math.min(minCost, dp[finalMask][end] + dist[end][start]);
        }
    }
    
    return minCost;
}

2. Subset Sum Problems

State compression is useful for problems involving finding optimal subsets from a set of elements.

Example: Partition Array to Minimize Sum Difference

Given an array, partition it into two subsets such that the difference between the sums of the subsets is minimized.

State: dp[mask] = sum of elements in the subset represented by mask
Approach: Generate all possible subset sums and find the minimum difference

// Partition array to minimize sum difference
int minSubsetSumDifference(int[] nums) {
    int n = nums.length;
    int totalSum = 0;
    
    for (int num : nums) {
        totalSum += num;
    }
    
    // Generate all possible subset sums using bit manipulation
    boolean[] possible = new boolean[totalSum + 1];
    possible[0] = true;
    
    for (int num : nums) {
        for (int j = totalSum; j >= num; j--) {
            possible[j] |= possible[j - num];
        }
    }
    
    // Find the subset sum closest to totalSum/2
    int minDiff = totalSum;
    for (int j = 0; j <= totalSum / 2; j++) {
        if (possible[j]) {
            minDiff = Math.min(minDiff, totalSum - 2 * j);
        }
    }
    
    return minDiff;
}

3. Hamiltonian Path Problems

Finding paths that visit each vertex exactly once in a graph.

DP Formulation:

State: dp[mask][v] = whether there exists a path that visits exactly the vertices in mask and ends at vertex v
Recurrence: dp[mask][v] = OR of dp[mask ^ (1 << v)][u] for all u such that there is an edge from u to v

4. Tips for State Compression DP

Practical Considerations:

State Space Limitation: This approach typically works well for n ≤ 20 due to the 2^n state space
Bit Manipulation: Familiarize yourself with bit operations (set, clear, check bits)
Memory Optimization: Consider using a map instead of an array for sparse state spaces
Iterating Over Subsets: Learn efficient ways to iterate over all subsets or submasks

// Useful bit manipulation operations for state compression DP

// Check if bit i is set in mask
boolean isBitSet(int mask, int i) {
    return (mask & (1 << i)) != 0;
}

// Set bit i in mask
int setBit(int mask, int i) {
    return mask | (1 << i);
}

// Clear bit i in mask
int clearBit(int mask, int i) {
    return mask & ~(1 << i);
}

// Toggle bit i in mask
int toggleBit(int mask, int i) {
    return mask ^ (1 << i);
}

// Count set bits in mask
int countSetBits(int mask) {
    int count = 0;
    while (mask > 0) {
        count += mask & 1;
        mask >>= 1;
    }
    return count;
}

// Iterate through all subsets of a set (represented by mask)
void iterateSubsets(int mask) {
    for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
        // Process submask
        System.out.println(Integer.toBinaryString(submask));
    }
}

Interval DP

Interval DP is used to solve problems involving intervals or subarrays. The key idea is to compute results for smaller intervals first and then use them to build solutions for larger intervals.

1. Matrix Chain Multiplication

Given a sequence of matrices, find the most efficient way to multiply these matrices together to minimize the number of operations.

DP Formulation:

State: dp[i][j] = minimum cost to multiply matrices from i to j
Recurrence: dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost[i][k][j]) for all k where i ≤ k < j
Base Case: dp[i][i] = 0 (cost to multiply a single matrix is 0)

// Matrix Chain Multiplication using Interval DP
int matrixChainMultiplication(int[] dimensions) {
    int n = dimensions.length - 1; // Number of matrices
    int[][] dp = new int[n][n];
    
    // Fill the dp table
    for (int len = 1; len < n; len++) {
        for (int i = 0; i < n - len; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE;
            
            for (int k = i; k < j; k++) {
                // Cost = cost of multiplying matrices i to k + cost of multiplying matrices k+1 to j
                // + cost of multiplying the resulting matrices
                int cost = dp[i][k] + dp[k+1][j] + dimensions[i] * dimensions[k+1] * dimensions[j+1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    
    return dp[0][n-1];
}

2. Optimal Binary Search Tree

Given a sorted array of keys and their frequencies, construct a binary search tree that minimizes the total search cost.

DP Formulation:

State: dp[i][j] = minimum cost of optimal BST containing keys from i to j
Recurrence: dp[i][j] = min(dp[i][r-1] + dp[r+1][j] + sum of frequencies from i to j) for all r where i ≤ r ≤ j
Base Case: dp[i][i] = frequency[i]

3. Palindrome Partitioning

Partition a string such that every substring is a palindrome with minimum cuts.

DP Formulation:

State: dp[i][j] = minimum number of cuts needed for substring from i to j
Recurrence: If s[i..j] is a palindrome, dp[i][j] = 0, else dp[i][j] = min(dp[i][k] + dp[k+1][j] + 1) for all k where i ≤ k < j

// Palindrome Partitioning - Minimum Cuts
int minCuts(String s) {
    int n = s.length();
    
    // isPalindrome[i][j] = true if substring s[i..j] is a palindrome
    boolean[][] isPalindrome = new boolean[n][n];
    
    // dp[i] = minimum number of cuts needed for substring s[0..i]
    int[] dp = new int[n];
    
    // Initialize dp array
    for (int i = 0; i < n; i++) {
        dp[i] = i; // Maximum cuts needed (cut after each character)
    }
    
    // Fill isPalindrome table
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            
            if (s.charAt(i) == s.charAt(j) && (len <= 2 || isPalindrome[i+1][j-1])) {
                isPalindrome[i][j] = true;
                
                if (i == 0) {
                    dp[j] = 0; // No cuts needed for palindrome from start
                } else {
                    dp[j] = Math.min(dp[j], dp[i-1] + 1);
                }
            } else if (i < j) {
                // Try all possible cuts
                for (int k = i; k < j; k++) {
                    dp[j] = Math.min(dp[j], dp[k] + 1);
                }
            }
        }
    }
    
    return dp[n-1];
}

4. Burst Balloons

Given n balloons with values, burst them one by one to maximize the coins collected.

DP Formulation:

State: dp[i][j] = maximum coins obtained by bursting all balloons from i to j
Recurrence: dp[i][j] = max(dp[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]) for all k where i ≤ k ≤ j

Tree DP

Tree DP involves solving problems on tree data structures using dynamic programming. The key insight is to compute results for subtrees and combine them to solve the original problem.

1. Maximum Independent Set on Trees

Find the maximum independent set (no two vertices are adjacent) in a tree.

DP Formulation:

State: dp[node][0/1] = maximum independent set size for subtree rooted at node, where 0 means node is not included, 1 means node is included
Recurrence:
- dp[node][0] = sum of max(dp[child][0], dp[child][1]) for all children
- dp[node][1] = 1 + sum of dp[child][0] for all children

// Maximum Independent Set on Trees
class TreeNode {
    int val;
    List<TreeNode> children;
    
    TreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

int[] maxIndependentSet(TreeNode root) {
    if (root == null) return new int[]{0, 0};
    
    int includeRoot = 1; // Include the root
    int excludeRoot = 0; // Exclude the root
    
    for (TreeNode child : root.children) {
        int[] childResult = maxIndependentSet(child);
        
        // If we include the root, we can't include its children
        includeRoot += childResult[1];
        
        // If we exclude the root, we can either include or exclude each child
        excludeRoot += Math.max(childResult[0], childResult[1]);
    }
    
    return new int[]{includeRoot, excludeRoot};
}

// To get the final result, call this function and take the maximum
int getMaxIndependentSet(TreeNode root) {
    int[] result = maxIndependentSet(root);
    return Math.max(result[0], result[1]);
}

2. Diameter of a Tree

Find the length of the longest path between any two nodes in a tree.

DP Formulation:

State: height[node] = height of subtree rooted at node, diameter[node] = diameter of subtree rooted at node
Recurrence:
- height[node] = 1 + max(height[child]) for all children
- diameter[node] = max(diameter[child], max(height[child1] + height[child2] + 1)) for all pairs of children

// Diameter of a Tree
class TreeNode {
    int val;
    List<TreeNode> children;
    
    TreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

int diameter = 0;

int height(TreeNode root) {
    if (root == null) return 0;
    
    int maxHeight1 = 0;
    int maxHeight2 = 0;
    
    for (TreeNode child : root.children) {
        int childHeight = height(child);
        
        if (childHeight > maxHeight1) {
            maxHeight2 = maxHeight1;
            maxHeight1 = childHeight;
        } else if (childHeight > maxHeight2) {
            maxHeight2 = childHeight;
        }
    }
    
    // Update diameter: longest path through this node
    diameter = Math.max(diameter, maxHeight1 + maxHeight2);
    
    return 1 + maxHeight1; // Height of this subtree
}

// To get the final result, call height() and return diameter
int treeDiameter(TreeNode root) {
    height(root);
    return diameter;
}

3. Binary Tree Camera

Place minimum number of cameras on binary tree nodes such that all nodes are monitored.

DP Formulation:

State: dp[node][state] where state can be:
- 0: Node is not monitored
- 1: Node is monitored but has no camera
- 2: Node has a camera
Recurrence: Depends on the states of the children nodes

4. Tree Coloring

Color a tree with k colors such that no two adjacent nodes have the same color.

DP Formulation:

State: dp[node][color] = number of ways to color the subtree rooted at node with the node colored with 'color'
Recurrence: dp[node][color] = product of (sum of dp[child][other_colors]) for all children

Digit DP

Digit DP is used to solve problems that involve counting numbers with specific digit properties within a range. This technique is particularly useful for problems that ask for counts of numbers with certain digit constraints.

1. Count Numbers with Sum of Digits Equal to X

Count numbers in range [a, b] where the sum of digits equals a given value X.

DP Formulation:

State: dp[pos][sum][tight] = count of valid numbers when considering digits from position 'pos' onwards, with current digit sum 'sum', and 'tight' indicating whether we're constrained by the upper bound
Recurrence: Sum over all possible digits at the current position, considering the constraints

// Count numbers with digit sum equal to X
class DigitDP {
    int[][][] dp;
    String upperBound;
    
    int countNumbersWithDigitSum(int a, int b, int targetSum) {
        // Count numbers from 1 to b with digit sum = targetSum
        int countB = countUpTo(String.valueOf(b), targetSum);
        
        // Count numbers from 1 to a-1 with digit sum = targetSum
        int countA = countUpTo(String.valueOf(a-1), targetSum);
        
        return countB - countA;
    }
    
    int countUpTo(String num, int targetSum) {
        upperBound = num;
        int n = num.length();
        
        // dp[pos][sum][tight]
        dp = new int[n][targetSum + 1][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= targetSum; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        
        return digitDp(0, 0, 1);
    }
    
    int digitDp(int pos, int sum, int tight) {
        // Base case: reached the end of number
        if (pos == upperBound.length()) {
            return sum == 0 ? 1 : 0;
        }
        
        // If already computed
        if (dp[pos][sum][tight] != -1) {
            return dp[pos][sum][tight];
        }
        
        int result = 0;
        int limit = tight == 1 ? upperBound.charAt(pos) - '0' : 9;
        
        // Try all possible digits at current position
        for (int digit = 0; digit <= limit; digit++) {
            // Calculate new sum and tight flag
            int newSum = sum - digit;
            int newTight = tight == 1 && digit == limit ? 1 : 0;
            
            // Only proceed if new sum is valid
            if (newSum >= 0) {
                result += digitDp(pos + 1, newSum, newTight);
            }
        }
        
        // Memoize and return
        return dp[pos][sum][tight] = result;
    }
}

2. Count Numbers with No Consecutive 1's in Binary Representation

Count numbers in range [a, b] whose binary representation has no consecutive 1's.

DP Formulation:

State: dp[pos][last][tight] = count of valid numbers when considering bits from position 'pos' onwards, with 'last' being the last bit used, and 'tight' indicating whether we're constrained by the upper bound
Recurrence: Sum over all possible bits (0 or 1) at the current position, considering the constraints

3. Count Numbers with Digit d Appearing k Times

Count numbers in range [a, b] where digit d appears exactly k times.

DP Formulation:

State: dp[pos][count][tight] = count of valid numbers when considering digits from position 'pos' onwards, with digit d appearing 'count' times so far, and 'tight' indicating whether we're constrained by the upper bound
Recurrence: Sum over all possible digits at the current position, considering the constraints

4. Tips for Digit DP

Common Patterns:

Tight Flag: Always use a tight flag to handle the upper bound constraint
Leading Zeros: Sometimes you need a flag to handle leading zeros
Memoization: Always memoize to avoid recomputing the same states
Range Queries: For range [a, b], compute for [1, b] and subtract [1, a-1]
State Design: Carefully design the state to capture all necessary information

DP Optimization Techniques

For certain types of DP problems, we can apply optimization techniques to reduce the time complexity from O(n³) or worse to O(n²) or better.

1. Knuth's Optimization

Applicable when the DP recurrence has the form: dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C[i][j] for i ≤ k < j, and the optimal k for dp[i][j] lies between the optimal k for dp[i][j-1] and dp[i+1][j].

Requirements:

Monotonicity: If opt[i][j] represents the optimal k for dp[i][j], then opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]
Quadrangle Inequality: For all a ≤ b ≤ c ≤ d, C[a][c] + C[b][d] ≤ C[a][d] + C[b][c]

// Knuth's Optimization Example: Optimal Binary Search Tree
int optimalBST(int[] keys, int[] freq) {
    int n = keys.length;
    int[][] dp = new int[n+1][n+1];
    int[][] opt = new int[n+1][n+1]; // Stores optimal k values
    
    // Initialize for single keys
    for (int i = 1; i <= n; i++) {
        dp[i][i] = freq[i-1];
        opt[i][i] = i;
    }
    
    // Fill dp table using Knuth's optimization
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            
            // Calculate sum of frequencies from i to j
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += freq[k-1];
            }
            
            // Use the optimal k values from smaller problems
            for (int k = opt[i][j-1]; k <= opt[i+1][j]; k++) {
                int val = (k > i ? dp[i][k-1] : 0) + (k < j ? dp[k+1][j] : 0) + sum;
                if (val < dp[i][j]) {
                    dp[i][j] = val;
                    opt[i][j] = k;
                }
            }
        }
    }
    
    return dp[1][n];
}

2. Convex Hull Optimization

Applicable when the DP recurrence has the form: dp[i] = min(dp[j] + b[j] * a[i]) for j < i, and certain convexity properties hold.

Requirements:

Monotonicity: a[i] is non-decreasing
Convexity: b[j] is non-increasing

3. Divide and Conquer Optimization

Applicable when the DP recurrence has the form: dp[i][j] = min(dp[i-1][k] + C[k][j]) for k < j, and the optimal k for dp[i][j] is non-decreasing with j.

Approach:

Instead of trying all k for each j, use divide and conquer to find the optimal k
Reduces time complexity from O(n³) to O(n² log n)

4. Monotone Queue Optimization

Applicable when the DP recurrence involves finding the minimum or maximum over a sliding window.

Example: Sliding Window Minimum

Use a deque to maintain a monotonic queue of potential minimums
Reduces time complexity from O(n²) to O(n)

Practice Problems

Test your understanding of hard dynamic programming concepts with these challenging problems.

1. Longest Palindromic Subsequence

MediumInterval DP

Find the length of the longest subsequence that is a palindrome.

View Problem →

2. Partition Array for Maximum Sum

MediumInterval DP

Partition an array into subarrays of length at most K to maximize the sum of each subarray's maximum element.

View Problem →

3. Number of Ways to Form a Target String

HardString DP

Count the number of ways to form a target string by selecting characters from words.

View Problem →

4. Minimum Cost to Merge Stones

HardInterval DP

Merge piles of stones with minimum cost, where merging K piles costs the sum of their weights.

View Problem →

5. Count Different Palindromic Subsequences

HardInterval DP

Count the number of different palindromic subsequences in a string.

View Problem →

6. Numbers With Repeated Digits

HardDigit DP

Count numbers from 1 to N that have at least one repeated digit.

View Problem →

7. Binary Trees With Factors

MediumTree DP

Count the number of binary trees where each non-leaf node's value is the product of its children.

View Problem →

8. Minimum Score Triangulation

MediumInterval DP

Find the minimum score of a triangulation of a convex polygon.

View Problem →