Dynamic Programming • Optimization

DP with Binary Search

Combine Dynamic Programming with Binary Search to optimize specific state transitions from O(N) down to O(log N).

Overview

In certain DP patterns, the state space or transition logic exhibits monotonicity. We can exploit this to search for the optimal transition in logarithmic time.

The LIS Example

The standard Longest Increasing Subsequence takes O(N^2) because we scan all previous elements. By maintaining a sorted `tails` array, we can binary search the scan in O(log N).

Job Scheduling

Another classic is Weighted Job Scheduling. By sorting jobs by end time, we can binary search to find the latest non-overlapping job, making it O(N log N).

Key Insight

If you see a nested O(N^2) loop where the inner loop is just looking for a threshold (like the first number larger than X), it begs for Binary Search.

10

9

2

5

3

7

101

18

Tails Array (Length = LIS)

[ Empty ]

Code Tracker

:::

1let tails = [];

2for (let x of nums) {

3 let low = 0, high = tails.length;

4 while (low < high) {

5 let mid = Math.floor((low + high) / 2);

6 if (tails[mid] < x) low = mid + 1;

7 else high = mid;

8 }

9 if (low === tails.length) tails.push(x);

10 else tails[low] = x;

11}

Dp With Binary Search

Dp With Binary Search

DP with Binary Search

Overview

The LIS Example

Job Scheduling

Key Insight

DP with Binary Search

Overview

The LIS Example

Job Scheduling

Key Insight