Dynamic Programming • Optimization

DP Optimization Techniques

An overview of advanced techniques to reduce time and space complexities in dynamic programming.

Space Optimization

If state `dp[i]` only relies on `dp[i-1]`, we can drop the `i` dimension entirely. This reduces memory usage drastically (e.g. O(N^2) to O(N)).

Divide and Conquer and Knuth Optimization rely on the fact that the optimal choice `k` for state `(i, j)` is bounded by choices for adjacent states.

The Convex Hull trick treats DP transitions as linear equations `y = mx + c` and queries the minimum `y` across an envelope of intersecting lines.

Matrix Exponentiation can solve linear recurrence relations (like Fibonacci) in O(log N) time instead of O(N).

Space OptO(N^2) → O(N)

D&C OptO(N^3) → O(N^2 log N)

Convex HullO(N^2) → O(N)

Knuth OptO(N^3) → O(N^2)

Code Tracker

:::

1// 1. Space Optimization: O(N) instead of O(N^2)

2// 2. Divide and Conquer Optimization: O(N log N)

3// 3. Convex Hull Trick: Intersecting lines, O(N)

4// 4. Knuth Optimization: opt[i][j-1] <= opt[i][j] <= opt[i+1][j]

5// 5. Matrix Exponentiation: O(log N) for linear recurrences