Algorithms
Advanced DP Techniques
Difficulty: Advanced
Standard tabulation gets you O(n^2) DP. The Convex Hull Trick brings the same recurrence down to O(n log n) whenever the transition is a linear function of the previous state, and the speedup matters: contest problems with n = 10^5 go...
Advanced DP Techniques
Standard tabulation gets you O(n^2) DP. The Convex Hull Trick brings the same recurrence down to O(n log n) whenever the transition is a linear function of the previous state, and the speedup matters: contest problems with n = 10^5 go from too-slow to fast enough on exactly that change. A whole sub-field of DP is dedicated to these recurrence-shaped optimizations, and this lesson is your entry into it.
Advanced DP Techniques covers four directions of post-tabulation DP. Optimization methods include the Convex Hull Trick (offline sorted-slope and online Li Chao tree), Divide and Conquer DP for monotone-split problems, and Knuth's Optimization for optimal-BST-style recurrences. Digit DP teaches you how to count numbers with properties in a range [L, R] by carrying a tight-constraint flag through the recursion. Advanced bitmask DP solves TSP, Hamiltonian path, and grid-tiling profile DP. Probability DP turns recurrences over expected values into clean tables, and Kadane's algorithm generalizes to circular and 2D variants.
In Dynamic Programming (Advanced), you mastered multi-dimensional state and transitions. This lesson asks the next question: when the table is too big or the transition too slow, how do you optimize?
Next, Graph Algorithms (Advanced) brings similar depth to graph theory.
Prerequisites:
Dynamic Programming (Advanced)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Apply the Convex Hull Trick to optimize DP transitions that involve linear functions.
Implement digit DP to count numbers with specific digit properties in a range.
Solve the Traveling Salesman Problem using bitmask DP and explain its time complexity.
Implement Kadane's algorithm and extend it to the circular maximum subarray variant.
Recognize when Divide and Conquer DP or Knuth's Optimization can reduce DP complexity.
Analyze the time and space complexity of each DP optimization technique.
Why This Matters
01
DP optimization techniques like the Convex Hull Trick reduce O(n^2) DP to O(n log n), making previously infeasible problems solvable within time limits.
02
Digit DP is the standard technique for counting numbers with specific properties in a range — a common competitive programming pattern that appears in number theory problems.
03
Kadane's algorithm for maximum subarray sum is one of the most frequently asked interview questions, and its circular and 2D extensions test deep understanding.
04
Advanced bitmask DP enables solving NP-hard problems (like TSP) exactly for small inputs, a technique used in both competitions and real-world optimization.
Key Terms
8 terms you'll encounter in this lesson
Convex Hull Trick
A technique to optimize DP transitions of the form dp[i] = min(dp[j] + b[j]*a[i]) where a[i] and b[j] are known values. Maintains a set of linear functions and queries the optimal one in O(log n) or amortized O(1).
Divide and Conquer DP
When the optimal split point for dp[i][j] is monotone in j, we can use divide and conquer to reduce O(n*m*k) DP to O(n*m*log k). The key insight is that opt[i][j] <= opt[i][j+1].
Knuth's Optimization
Reduces O(n^3) interval DP to O(n^2) when the cost function satisfies the quadrangle inequality. Used in optimal BST and similar problems where opt[i][j-1] <= opt[i][j] <= opt[i+1][j].
Digit DP
A DP technique for counting integers in a range [L,R] with specific digit properties. State typically includes the current digit position, whether we're still bounded by the limit, and problem-specific flags.
Kadane's Algorithm
An O(n) algorithm for finding the maximum subarray sum. Maintains a running sum and resets when it goes negative. The classic example of converting a 2D DP problem to O(n) using a single variable.
Circular Subarray
A variant where the array wraps around. The maximum circular subarray sum equals max(standard Kadane, total_sum - minimum subarray sum), handling the wrap-around case.
Profile DP
A bitmask DP technique for grid-filling problems where the state encodes the profile (shape) of the boundary between filled and unfilled cells. Used in domino/tromino tiling problems.
Probability DP
DP where states represent expected values or probabilities. Transitions multiply or add probabilities. Common in dice problems and random walk analysis.
Heads Up
Common misconceptions to watch out for
"Kadane's algorithm always starts from index 0"
Kadane's can start from any index. The key is that currentSum resets to the current element whenever the running sum goes negative. The maximum subarray can start and end at any position.
"The Convex Hull Trick always gives O(1) per query"
Amortized O(1) per query only works when queries come in sorted order (monotone). In the general case, you need a Li Chao tree or sorted structure for O(log n) per query.
"Digit DP only works for single numbers, not ranges"
Digit DP naturally works on ranges [0, N]. For a range [L, R], compute count(R) - count(L-1). This subtraction trick is fundamental to the technique.
"Bitmask DP for TSP gives the optimal tour in polynomial time"
Bitmask DP for TSP runs in O(2^n * n^2), which is exponential. It is exact but only feasible for small n (around 20). TSP remains NP-hard — no polynomial-time exact algorithm is known.