All Roadmaps›🧠 Data Structures & Algorithms›Phase 3›Dynamic Programming — Introduction & Thinking

Dynamic Programming — Introduction & Thinking

0/12 in this phase0/57 across the roadmap

📖 Concept

Dynamic Programming (DP) solves problems by breaking them into overlapping sub-problems and storing results to avoid recomputation. It's the single most important topic for coding interviews.

When to use DP:

  1. Optimal substructure — optimal solution is built from optimal sub-solutions
  2. Overlapping sub-problems — same sub-problems are solved multiple times

DP vs other techniques:

  • D&C — sub-problems are INDEPENDENT (no overlap) → merge sort
  • Greedy — make local optimal choice, no backtracking → activity selection
  • DP — sub-problems OVERLAP, need to consider ALL options → knapsack

Two approaches:

  1. Top-Down (Memoization) — Start from the big problem, recurse down, cache results
  2. Bottom-Up (Tabulation) — Start from smallest sub-problems, build up to the answer

The DP thinking process:

  1. Define the state — What does dp[i] represent?
  2. Find the recurrence — How does dp[i] relate to smaller states?
  3. Identify the base case — What are the smallest sub-problems?
  4. Determine the order — Which states must be computed first?
  5. Compute the answer — Where in the table is the final answer?

Common DP patterns:

  • Linear DP: dp[i] depends on dp[i-1], dp[i-2], ...
  • Grid DP: dp[i][j] depends on dp[i-1][j], dp[i][j-1], ...
  • Interval DP: dp[i][j] = optimal over range [i, j]
  • Knapsack: dp[i][w] = best using first i items with capacity w

🏠 Real-world analogy: DP is like writing an exam booklet. If question 5 asks "what was the answer to question 3?", you don't re-solve question 3 — you look back at your already-written answer.

💻 Code Example

codeTap to expand ⛶
1// FIBONACCI — The gateway to DP
2

3// Naive recursion: O(2ⁿ) time — TERRIBLE
4function fibNaive(n) {
5  if (n <= 1) return n;
6  return fibNaive(n - 1) + fibNaive(n - 2);
7}
8

9// Top-Down (Memoization): O(n) time, O(n) space
10function fibMemo(n, memo = {}) {
11  if (n <= 1) return n;
12  if (memo[n]) return memo[n];
13  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
14  return memo[n];
15}
16

17// Bottom-Up (Tabulation): O(n) time, O(n) space
18function fibTab(n: number): number {
19  if (n <= 1) return n;
20  const dp = new Array(n + 1);
21  dp[0] = 0; dp[1] = 1;
22  for (let i = 2; i <= n; i++) {
23    dp[i] = dp[i - 1] + dp[i - 2];
24  }
25  return dp[n];
26}
27

28// Space-Optimized: O(n) time, O(1) space
29function fibOptimal(n: number): number {
30  if (n <= 1) return n;
31  let prev = 0, curr = 1;
32  for (let i = 2; i <= n; i++) {
33    [prev, curr] = [curr, prev + curr];
34  }
35  return curr;
36}
37

38// CLIMBING STAIRS — Easy DP
39function climbStairs(n: number): number {
40  if (n <= 2) return n;
41  let prev = 1, curr = 2;
42  for (let i = 3; i <= n; i++) {
43    [prev, curr] = [curr, prev + curr];
44  }
45  return curr;
46}
47// dp[i] = dp[i-1] + dp[i-2] — same as fibonacci!
48

49// MINIMUM COST CLIMBING STAIRS
50function minCostClimbing(cost: number[]): number {
51  const n = cost.length;
52  const dp = new Array(n + 1).fill(0);
53  for (let i = 2; i <= n; i++) {
54    dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
55  }
56  return dp[n];
57}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Fibonacci with memoization and tabulation
  2. Climbing stairs — ways to reach step n (1 or 2 steps at a time)
  3. Min cost climbing stairs
  4. House robber — max money without robbing adjacent houses
  5. Maximum subarray (Kadane's algorithm as DP)
  6. Decode ways — count decodings of a digit string
  7. Longest increasing subsequence
  8. Coin change — minimum coins to make amount
  9. Word break — can string be segmented into dictionary words?
  10. Longest common subsequence of two strings

⚠️ Common Mistakes

  • Not identifying overlapping sub-problems — if sub-problems are independent, use D&C instead

  • Forgetting the base case — every DP needs properly initialized base cases

  • Wrong state definition — if dp[i] doesn't clearly represent something, the recurrence will be wrong

  • Not optimizing space — many 1D DP problems only need the last 1-2 values, not the full array

  • Jumping to DP without trying simpler approaches first — greedy or brute force may be sufficient

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Dynamic Programming — Introduction & Thinking

← PreviousGreedy AlgorithmsNext →DP — 1D Problems (Fibonacci, Climbing Stairs, House Robber)