Dynamic Programming • Pattern

DP on Subsequences

Subsequence problems involve iterating through an array and making a "Pick" or "Skip" decision for each element.

Overview

Subsequences (unlike substrings) don't have to be contiguous. The most common pattern is generating subsets to hit a specific sum or property.

The Decision Tree

For every element at index `i`, we branch into two recursive paths: one where we include `nums[i]` in our subsequence, and one where we don't.

Memoization

Because there are 2^N total subsequences, brute force is too slow. But the number of distinct `(index, currentSum)` states is often small, allowing DP.

Knapsack Relation

The 0/1 Knapsack problem is the classic example of DP on subsequences. Each item is picked or skipped to maximize value within a weight limit.

[ ]

Code Tracker

:::

1function solve(idx, currentSum) {

2 if (idx === n) return currentSum === target;

3 if (dp[idx][currentSum] !== -1) return dp[idx][currentSum];

4

5 let skip = solve(idx + 1, currentSum);

6 let pick = solve(idx + 1, currentSum + nums[idx]);

7

8 return dp[idx][currentSum] = skip || pick;

9}

Dp On Subsequences

Dp On Subsequences

DP on Subsequences

Overview

The Decision Tree

Memoization

Knapsack Relation

DP on Subsequences

Overview

The Decision Tree

Memoization

Knapsack Relation