Dynamic Programming21 sections · 916 units
Open in Course

Intro

The Goal

In earlier sections, DP (dynamic programming) states were simple: the current index, the remaining capacity, the current sum. But some problems hide their states inside subsequences.

A subsequence is what you get by deleting some elements without changing the order. For [1, 2, 3, 4], the subsequences include [1, 3], [2, 4], and [1, 2, 3, 4]. There are 2n2^n of them. By the end, you'll solve LIS (Longest Increasing Subsequence) and its variations. This pattern appears everywhere in interviews and contests.