Dev Cookies

Posted on Sep 1

📝 Blog 10: DP Optimization Techniques 🚀

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 → meaning opt[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²) to O(n log n) in partition DP.
Convex Hull Trick → Optimizes linear/quadratic DP recurrences.
Knuth Optimization → Improves interval DP from O(n³) to O(n²).
Monotonic Queue DP → Handles sliding window transitions efficiently.

These techniques separate a good DP coder from a great one 💡.

DEV Community