# Dynamic Programming Fundamentals — Part 2: Interview Problems

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

## 1. Climbing 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
```

## 2. House 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
```

## 3. Coin 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
```

## 4. Longest 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)
```

## 5. Word 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]
```

## 6. Decode 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
```