Dynamic Programming Foundations

DP works when a problem has overlapping subproblems and optimal substructure.

Checklist

1. Define state clearly
2. Write transition relation
3. Set base cases
4. Choose top-down or bottom-up

Practice

• Climbing Stairs
• Coin Change
• Minimum Path Sum
• Edit Distance
• Distinct Subsequences