Dynamic Programming mind map

Tabulate overlapping subproblems for optimal answers.

Core idea: State is the smallest reusable question; transition is the last choice.

Mnemonic: State → transition → order · Cost: States × transitions

Line: Previous-state recurrence

Signal: Position i depends on a few earlier positions or modes.

Move: Name dp[i] precisely, seed the smallest states, and compress history when only neighbors matter.

Examples: Climbing Stairs, House Robber, Stock Cooldown

Signal: Items consume capacity, form a target, or may be reused.

Move: Transition from skipping or taking; loop capacity backward for 0/1 and forward for reuse.

Examples: Coin Change, Partition Equal Subset, Target Sum

Signal: A state receives answers from directional predecessors or children.

Move: Topologically order dependencies, then combine every legal predecessor exactly once.

Examples: Unique Paths, Minimum Path Sum, Tree Robber

Signal: Two prefixes or a shrinking interval define the reusable question.

Move: Use 2D prefix states, or solve shorter intervals before longer ones.

Examples: Longest Common Subsequence, Edit Distance, Longest Palindrome