Top Dynamic Programming Patterns

1D Linear DP

dp[i] = best answer for prefix ending at i. Examples: climbing stairs, house robber, max subarray sum. Sometimes dp[i] depends on dp[i-1] and dp[i-2] or a range.

2D Grid DP

dp[i][j] = answer to reach (i, j). Direction: from top-left, or from bottom-right. Examples: unique paths, min path sum, dungeon game.

Knapsack

• 0/1: Each item once. dp[w] or dp[i][w].
• Unbounded: Same item repeatable. Iterate w forward in 1D.

Longest Common Subsequence and Variants

dp[i][j] on two strings. Edit distance, LCS, delete operations for two strings—same family.

State Machine

Sometimes state is (position, flag). Examples: buy/sell stock with cooldown, max profit with at most K transactions.

Summary

Identify "optimal substructure" and "overlapping subproblems," then define state and recurrence. Practice each pattern on Preplume(/).