Dynamic Programming (DP) is powerful, but it often suffers from time complexity (O(n²)
or O(n³)
) and space complexity (O(n*m)
).
This is where DP Optimization Techniques come in — they let us solve problems that would otherwise be impossible within time limits.
In this blog, we’ll cover 5 essential DP optimization methods every advanced developer and competitive programmer must know:
- Space Optimization (Rolling Arrays)
- Divide & Conquer DP
- Convex Hull Trick (CHT)
- Knuth Optimization
- DP with Monotonic Queue
Let’s go step by step.
1️⃣ Space Optimization (Rolling Arrays)
Many DP problems only depend on the previous row or column.
Instead of storing the entire dp[n][m]
, we can just store two rows (current + previous).
Example: Longest Common Subsequence (LCS)
class LCS {
public int longestCommonSubsequence(String s1, String s2) {
int n = s1.length(), m = s2.length();
int[] prev = new int[m+1];
int[] curr = new int[m+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
curr[j] = 1 + prev[j-1];
} else {
curr[j] = Math.max(prev[j], curr[j-1]);
}
}
prev = curr.clone(); // roll arrays
}
return prev[m];
}
}
✅ Space reduced from O(n*m) → O(m).
This technique is widely used in LCS, Knapsack, Edit Distance, LIS variants.
2️⃣ Divide & Conquer DP
This optimization applies when:
dp[i][j] = min_{k < j}(dp[i-1][k] + C[k][j])
- The optimal partition point (
k
) is monotonic → meaningopt[i][j] <= opt[i][j+1]
.
This lets us compute each row in O(n log n)
instead of O(n²)
.
Example: Partitioning an Array into K Groups
class DivideAndConquerDP {
static int INF = 1_000_000_000;
int[][] dp, opt;
public void compute(int i, int l, int r, int optL, int optR, int[] cost) {
if (l > r) return;
int mid = (l + r) / 2;
int bestK = -1;
dp[i][mid] = INF;
for (int k = optL; k <= Math.min(mid, optR); k++) {
int val = dp[i-1][k] + cost[mid] - cost[k];
if (val < dp[i][mid]) {
dp[i][mid] = val;
bestK = k;
}
}
compute(i, l, mid-1, optL, bestK, cost);
compute(i, mid+1, r, bestK, optR, cost);
}
}
✅ Used in text segmentation, scheduling, partition problems.
3️⃣ Convex Hull Trick (CHT)
If DP looks like:
dp[i] = min_{j < i}(dp[j] + m[j]*x[i] + c[j])
We can treat each transition as a line equation (y = m*x + c
) and use a Convex Hull of lines to answer queries efficiently.
Example: DP with Linear Costs
class ConvexHullDP {
static class Line {
long m, c;
Line(long m, long c) { this.m = m; this.c = c; }
long eval(long x) { return m * x + c; }
}
Deque<Line> hull = new ArrayDeque<>();
boolean bad(Line l1, Line l2, Line l3) {
return (l3.c - l1.c) * (l1.m - l2.m) < (l2.c - l1.c) * (l1.m - l3.m);
}
void addLine(long m, long c) {
Line l = new Line(m, c);
while (hull.size() >= 2) {
Line l2 = hull.removeLast();
Line l1 = hull.peekLast();
if (bad(l1, l2, l)) {
continue;
} else {
hull.addLast(l2);
break;
}
}
hull.addLast(l);
}
long query(long x) {
while (hull.size() >= 2 && hull.getFirst().eval(x) >= hull.get(1).eval(x)) {
hull.removeFirst();
}
return hull.getFirst().eval(x);
}
}
✅ Used in DP with quadratic/linear costs, like Divide array into segments, speed optimization problems.
4️⃣ Knuth Optimization
This reduces O(n³) → O(n²) in interval DP problems like Matrix Chain Multiplication, Optimal BST, and Merging Stones.
- Works when the “optimal split point” is monotonic:
opt[i][j-1] <= opt[i][j] <= opt[i+1][j]
.
Example: Matrix Chain Multiplication
class KnuthOptimization {
public int matrixChainOrder(int[] dims) {
int n = dims.length - 1;
int[][] dp = new int[n][n];
int[][] opt = new int[n][n];
for (int i = 0; i < n; i++) opt[i][i] = i;
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = opt[i][j-1]; k <= opt[i+1][j]; k++) {
int cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1];
if (cost < dp[i][j]) {
dp[i][j] = cost;
opt[i][j] = k;
}
}
}
}
return dp[0][n-1];
}
}
✅ Used in parsing, merging files, matrix multiplication, stone merging.
5️⃣ DP with Monotonic Queue
This applies when DP recurrence involves a sliding window minimum/maximum.
We maintain a deque to get the best candidate in O(1) amortized per step.
Example: Sliding Window DP
Problem: dp[i] = arr[i] + min(dp[i-k...i-1])
class MonotonicQueueDP {
public int minCost(int[] arr, int k) {
int n = arr.length;
int[] dp = new int[n];
Deque<Integer> dq = new ArrayDeque<>();
dp[0] = arr[0];
dq.add(0);
for (int i = 1; i < n; i++) {
while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();
dp[i] = arr[i] + dp[dq.peekFirst()];
while (!dq.isEmpty() && dp[dq.peekLast()] >= dp[i]) dq.pollLast();
dq.add(i);
}
return dp[n-1];
}
}
✅ Used in constrained subsequence problems, knapsack with window, shortest path in DAG-like structures.
🏁 Wrap-Up
- Space Optimization → Save memory (Knapsack, LCS, Edit Distance).
-
Divide & Conquer DP → Reduces
O(n²)
toO(n log n)
in partition DP. - Convex Hull Trick → Optimizes linear/quadratic DP recurrences.
-
Knuth Optimization → Improves interval DP from
O(n³)
toO(n²)
. - Monotonic Queue DP → Handles sliding window transitions efficiently.
These techniques separate a good DP coder from a great one 💡.
Top comments (0)