Dynamic Programming

Summary

Solving problems by breaking them into overlapping subproblems and caching results — usually the hardest interview topic, but a small set of patterns covers most questions.

• 1Learn to recognize DP problems: optimal substructure and overlapping subproblems.
• 2Practice the classic patterns: knapsack, longest common subsequence, climbing stairs variants.
• 3Always write the brute-force recursive solution first, then add memoization.