Dynamic Programming

Break problems into overlapping subproblems, cache results, and build up to the final answer.

When to use

• Optimal substructure + overlapping subproblems
• Counting ways
• Min/max optimization
• String matching

When NOT to use

• No overlapping subproblems (use divide and conquer)
• Greedy works and is simpler

Common traps

• Wrong state definition
• Wrong transition formula
• Not initializing base cases
• Off-by-one in table dimensions

Key Invariant

Define the state clearly, write the recurrence, then decide top-down (memo) or bottom-up (table)

Problems (42)

#14Climbing Stairs

#58Counting Bits

#304Range Sum Query - Immutable

#15Maximum Subarray

#36House Robber

#70Longest Increasing Subsequence

#72Unique Paths

#73Min Cost Climbing Stairs

#75Maximum Product Subarray

#1360/1 Knapsack

#137Unbounded Knapsack

#138Longest Common Subsequence

#140Partition Equal Subset Sum

#142Coin Change II

#144Best Time to Buy and Sell Stock with Cooldown

#146Minimum Path Sum

#147Paint House

#148Arithmetic Slices

#149Maximal Square

#150Longest Palindromic Subsequence

#219Longest Palindromic Substring

#305Range Sum Query 2D - Immutable

#307Maximum Sum Circular Subarray

#100Edit Distance

#101Burst Balloons

#102Regular Expression Matching

#103Longest Valid Parentheses

#104Interleaving String

#139Palindrome Partitioning II

#143Distinct Subsequences

#145Best Time to Buy and Sell Stock IV

#284Longest Increasing Path in a Matrix

#287Cherry Pickup

#289Dungeon Game

#290Russian Doll Envelopes

#291Wildcard Matching