Dynamic programming
Name a repeated subproblem, define its answer, and build larger answers from smaller ones.
Start the first lesson ↗RECALLED
Ways at n equal ways at n−1 plus ways at n−2.
Climbing Stairs
Ways at n equal ways at n−1 plus ways at n−2.
House Robber
At each house choose between skipping it and taking it plus the best two back.
House Robber II
First and last cannot both be used, so split into two linear cases.
Longest Palindromic Substring
Every palindrome expands from one character or one gap.
Palindromic Substrings
Each successful center expansion corresponds to one distinct substring occurrence.
Decode Ways
A position can be reached from one valid digit or one valid two-digit number.
Coin Change
Each amount depends on smaller amounts reached by removing one coin.
Maximum Product Subarray
A negative value swaps the roles of largest and smallest ending products.
Word Break
A prefix is solvable if some earlier solvable cut is followed by a dictionary word.
Longest Increasing Subsequence
The smallest possible tail for each length leaves maximum room to extend.
Unique Paths
Ways to a cell equal ways from above plus ways from left.
Longest Common Subsequence
Matching characters extend the diagonal answer; mismatches drop one side.
Combination Sum IV
Order matters, so every final choice extends all sequences for the remaining amount.