IRInterview Ready
← All patterns

Dynamic Programming

Break a problem into overlapping subproblems, solve each once, and cache the result (memoization or tabulation).

When to use it

  • Optimization problems (min/max cost, count ways) with overlapping subproblems and optimal substructure.
  • Problems that a naive recursive brute force would re-solve the same subproblem exponentially many times.

Signals in the problem statement

  • Keywords: 'number of ways', 'minimum/maximum cost', 'can you reach/partition'.
  • Recursive brute force has exponential time due to repeated subproblems.

Common pitfalls

  • Not identifying the correct state (what varies between subproblems) — the hardest part of DP.
  • Off-by-one base cases; forgetting to handle empty-input edge cases.

Practice Problems

Coin Change (Minimum Coins)

Medium

Asked at: Amazon, Google, Uber

Given coin denominations and a target amount, return the fewest number of coins needed to make that amount (or -1 if impossible).

Time: O(amount * numCoins) · Space: O(amount)

Longest Common Subsequence

Medium

Asked at: Amazon, Microsoft, Google

Given two strings, return the length of their longest common subsequence.

Time: O(m*n) · Space: O(m*n) (reducible to O(min(m,n)))

Climbing Stairs

Easy

Asked at: Amazon, Adobe

You can climb 1 or 2 steps at a time. How many distinct ways can you climb to the top of n steps?

Time: O(n) · Space: O(1)