Algorithms & Coding Interviews · Greedy, DP & Bits

Dynamic Programming Fundamentals

Dynamic programming turns exponential recursion into polynomial time by solving each subproblem once. Learn the five-step recipe (state, transition, base, order, answer), top-down vs bottom-up, the common 1D families, and watch House Robber, Coin Change and LIS fill their tables step by step.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 10 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Recognizing optimal substructure and overlapping subproblems
The five-step recipe and complexity = states × work
Top-down memoization vs bottom-up tables
Six classic 1D DP problems animated

📚 Before you start

Part 1The Pattern

Dynamic programming solves problems whose brute force recomputes the same subproblems again and again. You define the answer for a smaller state, express it through even smaller states (the transition), and store each result so it's computed once. Exponential recursion becomes polynomial. DP feels hard mostly because people skip the definition step; with a fixed recipe it becomes mechanical.

A DP table filled left to right from base cases

1When Is It DP?

Two properties:

Optimal substructure: the best answer for the whole problem is built from best answers to subproblems.
Overlapping subproblems: the recursion tree solves the same subproblem many times (Fibonacci's f(3) appears repeatedly).

Wording cues: "number of ways", "minimum/maximum cost", "longest/shortest … subsequence", "can you reach/form …", choices at each step that affect future options.

2The Five-Step Recipe

State: what does dp[i] (or dp[i][j]) mean, in one sentence? ("number of ways to reach step i")
Transition: how is dp[i] computed from smaller states? (dp[i] = dp[i−1] + dp[i−2])
Base cases: the smallest states with known answers (dp[0] = dp[1] = 1).
Order: compute states so dependencies are ready (increasing i).
Answer: which state is the final answer (dp[n]), and can you reduce space?

3Top-Down vs Bottom-Up

typescript

function climbMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return 1;
  if (memo.has(n)) return memo.get(n)!;
  const v = climbMemo(n - 1, memo) + climbMemo(n - 2, memo);
  memo.set(n, v);
  return v;
}

function climbTable(n: number): number {
  const dp = new Array(n + 1).fill(1);
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

function climbO1(n: number): number {
  let a = 1, b = 1;
  for (let i = 1; i < n; i++) [a, b] = [b, a + b];
  return b;
}

function climbBoth(n: number): number[] {
  return [climbMemo(n), climbTable(n), climbO1(n)];
}

python

from functools import lru_cache

def climb_memo(n):                          # top-down: recursion + cache
    @lru_cache(maxsize=None)
    def f(i):
        if i <= 1:
            return 1                        # base cases
        return f(i - 1) + f(i - 2)          # transition
    return f(n)

def climb_table(n):                         # bottom-up: fill a table in order
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def climb_o1(n):                            # space-optimized: keep only what's needed
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

def climb_both(n):
    return [climb_memo(n), climb_table(n), climb_o1(n)]

	Top-down (memoized recursion)	Bottom-up (tabulation)
writing it	natural from the recurrence	needs an explicit order
computes	only reachable states	every state
risk	recursion depth limits (Python ~1,000)	none
space optimization	hard	easy: keep only the last row(s)

A good interview flow: write the recurrence, code top-down quickly, then convert to bottom-up with O(1) or O(n) space if asked.

4Common 1D DP Families

Family	State	Transition
counting paths (stairs, decode ways)	ways to reach i	sum over the last step choices
take / skip (house robber)	best up to i	`max(skip: dp[i−1], take: dp[i−2] + a[i])`
unbounded choices (coin change)	best for amount a	`min over coins c: dp[a − c] + 1`
subsequence ending at i (LIS)	best ending exactly at i	max over earlier j that can precede i
segmentation (word break)	can prefix of length i be built?	any j with dp[j] and s[j:i] a word

Under the HoodWhy Memoization Changes Complexity▾

Complexity of a DP = (number of distinct states) × (work per state). Naive Fibonacci makes ~2ⁿ calls but has only n distinct states; with a cache each state is computed once, so it's O(n). Coin change has amount states × len(coins) choices = O(amount · k). Always state complexity in this form. Interviewers like hearing that you know where it comes from.

⚠️ Common Pitfalls

Vague state definitions ("dp[i] is the answer for i"): say exactly what it represents, including whether i is included or ending at.
Wrong base cases (dp[0] for "zero amount needs zero coins", "empty string decodes in one way").
Iterating in the wrong order so dp[i] reads values not yet computed.
Using greedy where choices interact (coin change).
Forgetting impossibility markers (inf for unreachable amounts, then mapping back to −1).

📋 Quick Reference

text

Recipe: state → transition → base → order → answer (→ shrink space)
Complexity = #states × work per state
take/skip: dp[i] = max(dp[i-1], dp[i-2] + a[i])
unbounded: dp[a] = min(dp[a-c] + 1 for c in coins)
top-down = recursion + cache · bottom-up = table in dependency order

Part 2Interview Problems

Six classic 1D DP problems, one for each common family: counting, take/skip, unbounded choices, subsequences, segmentation and decoding.

1Climbing Stairs (LeetCode 70)

🟢 Easy. You climb 1 or 2 steps at a time. How many distinct ways reach step n?

text

n = 3 → 3   (1+1+1, 1+2, 2+1)

Approach. ways(n) = ways(n − 1) + ways(n − 2): the last move was a 1-step or a 2-step. Base cases ways(0) = ways(1) = 1. Keep only the last two values.

Complexity. O(n) time, O(1) space.

typescript

function climbStairs(n: number): number {
  let a = 1, b = 1;
  for (let i = 1; i < n; i++) [a, b] = [b, a + b];
  return b;
}

python

def climb_stairs(n):
    a, b = 1, 1                    # ways(i-1), ways(i)
    for _ in range(n - 1):
        a, b = b, a + b
    return b

2House Robber (LeetCode 198)

🟠 Medium. Houses in a row hold money; you can't rob two adjacent houses. Return the maximum amount.

text

[2,7,9,3,1] → 12   (2 + 9 + 1)

Approach. Take/skip: best(i) = max(best(i − 1), best(i − 2) + nums[i]). Two rolling variables are enough.

Complexity. O(n) time, O(1) space.

typescript

function rob(nums: number[]): number {
  let prev2 = 0, prev1 = 0;
  for (const x of nums) [prev2, prev1] = [prev1, Math.max(prev1, prev2 + x)];
  return prev1;
}

python

def rob(nums):
    prev2, prev1 = 0, 0            # best up to i-2, best up to i-1
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

3Coin Change (LeetCode 322)

🟠 Medium. Return the fewest coins (unlimited supply of each denomination) that make amount, or −1.

text

coins = [1,2,5], amount = 11 → 3   (5 + 5 + 1)

Approach. dp[a] = fewest coins for amount a. dp[0] = 0; dp[a] = min(dp[a − c] + 1) over coins c ≤ a. Unreachable amounts stay infinite. Greedy fails here (coins [1,3,4], amount 6).

Complexity. O(amount · k) time, O(amount) space.

typescript

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins) if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
  return dp[amount] === Infinity ? -1 : dp[amount];
}

python

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

4Longest Increasing Subsequence (LeetCode 300)

🟠 Medium. Return the length of the longest strictly increasing subsequence.

text

[10,9,2,5,3,7,101,18] → 4   (2,3,7,18)

Approach. dp[i] = length of the longest increasing subsequence ending at i = 1 + max(dp[j]) over j < i with nums[j] < nums[i]: O(n²). The O(n log n) version keeps tails[k] = the smallest possible tail of an increasing subsequence of length k + 1 and binary-searches where each number goes.

Complexity. O(n²) DP, or O(n log n) with tails + binary search.

typescript

function lengthOfLIS(nums: number[]): number {
  // O(n^2) DP: dp[i] = longest increasing subsequence ending at i
  const dp = new Array(nums.length).fill(1);
  let best = nums.length ? 1 : 0;
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    best = Math.max(best, dp[i]);
  }
  return best;
}

python

from bisect import bisect_left

def length_of_lis(nums):
    tails = []                         # tails[k] = smallest tail of an IS of length k+1
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)            # extends the longest subsequence
        else:
            tails[i] = x               # a smaller tail for length i+1
    return len(tails)

5Word Break (LeetCode 139)

🟠 Medium. Can s be segmented into a sequence of dictionary words?

text

s = "applepenapple", dict = ["apple","pen"] → true

Approach. dp[i] = whether the prefix s[:i] can be segmented; dp[0] = true. dp[i] is true if some j < i has dp[j] true and s[j:i] in the dictionary (only check word lengths that exist).

Complexity. O(n · L) checks for maximum word length L.

typescript

function wordBreak(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict), lengths = [...new Set(wordDict.map((w) => w.length))];
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++)
    dp[i] = lengths.some((L) => L <= i && dp[i - L] && words.has(s.slice(i - L, i)));
  return dp[s.length];
}

python

def word_break(s, word_dict):
    words = set(word_dict)
    lengths = {len(w) for w in words}
    dp = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        dp[i] = any(L <= i and dp[i - L] and s[i - L:i] in words for L in lengths)
    return dp[-1]

6Decode Ways (LeetCode 91)

🟠 Medium. Letters map to 1…26. Count the ways to decode a digit string (a 0 can't start a code).

text

"226" → 3   (2 2 6, 22 6, 2 26)

Approach. dp[i] = ways to decode the first i characters. A single digit s[i−1] ≠ '0' adds dp[i−1]; a two-digit code s[i−2:i] between 10 and 26 adds dp[i−2]. Base dp[0] = 1.

Complexity. O(n) time, O(1) space with two variables.

typescript

function numDecodings(s: string): number {
  if (!s) return 0;
  let prev2 = 1, prev1 = s[0] !== "0" ? 1 : 0;
  for (let i = 2; i <= s.length; i++) {
    let cur = 0;
    if (s[i - 1] !== "0") cur += prev1;
    const two = Number(s.slice(i - 2, i));
    if (two >= 10 && two <= 26) cur += prev2;
    [prev2, prev1] = [prev1, cur];
  }
  return prev1;
}

python

def num_decodings(s):
    prev2, prev1 = 1, 1 if s and s[0] != "0" else 0     # dp[0], dp[1]
    for i in range(2, len(s) + 1):
        cur = 0
        if s[i - 1] != "0":
            cur += prev1
        if 10 <= int(s[i - 2:i]) <= 26:
            cur += prev2
        prev2, prev1 = prev1, cur
    return prev1 if s else 0

🧠 Key takeaways

DP needs optimal substructure and overlapping subproblems.
Recipe: state → transition → base cases → order → answer, then shrink space.
Complexity = number of states × work per state.
Families: counting, take/skip, unbounded choices, subsequence-ending-at-i, segmentation.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_dynamic_programming_fundamentals_exercise_1.py

TS PY

algo_dynamic_programming_fundamentals_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Why is memoized Fibonacci O(n)?

States × work.

2. House Robber transition:

Take or skip.

3. Coin Change dp[0] equals…

Zero coins for amount zero.

4. A main risk of top-down DP in Python?

~1,000 frames by default.

Source: algo_dynamic_programming_fundamentals_theory_1.md, algo_dynamic_programming_fundamentals_theory_2.md · generated by tools/build_lessons.py