Dynamic Programming • Pattern

DP on LIS Pattern

The Longest Increasing Subsequence (LIS) pattern is foundational for many sequence-based DP problems.

Overview

In LIS, we determine the longest sequence of strictly increasing elements. The DP state `dp[i]` stores the max length ending exactly at index `i`.

For every element `i`, we look back at all previous elements `j`. If `nums[i] > nums[j]`, we can extend the sequence ending at `j`.

This exact O(N^2) double-loop pattern solves variants like Longest Divisible Subset, Bitonic Subsequence, and Longest String Chain.

While the DP pattern is O(N^2), pure LIS length can be optimized to O(N log N) using binary search with a `tails` array.

10

dp: 1

9

dp: 1

2

dp: 1

5

dp: 1

3

dp: 1

7

dp: 1

101

dp: 1

18

dp: 1

Code Tracker

:::

1let dp = Array(n).fill(1);

2for (let i = 1; i < n; i++) {

3 for (let j = 0; j < i; j++) {

4 if (nums[i] > nums[j]) {

5 dp[i] = Math.max(dp[i], dp[j] + 1);

6 }

7 }

8}