26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

> *"Those who cannot remember the past are condemned to repeat it."*  
> DP subproblem ke answer ko memory me store kar leta hai taaki exponential $O(2^N)$ complexity polynomial $O(N)$ ban jaye!

---

### 2. LeetCode #70: Climbing Stairs ($O(N)$ Time, $O(1)$ Space)

$$dp[i] = dp[i-1] + dp[i-2]$$

```python
def climbStairs(n: int) -> int:
    one, two = 1, 1
    for _ in range(n - 1):
        one, two = one + two, one
    return one
```

---

### 3. LeetCode #198: House Robber ($O(N)$ Time, $O(1)$ Space)

*Rule:* Do adjacent houses rob nahi kar sakte!
$$dp[i] = \max(dp[i-1], \text{house}[i] + dp[i-2])$$

```python
def rob(nums: list[int]) -> int:
    rob1, rob2 = 0, 0
    # [rob1, rob2, num, num+1, ...]
    for num in nums:
        temp = max(num + rob1, rob2)
        rob1 = rob2
        rob2 = temp
    return rob2
```

---

### 4. LeetCode #322: Coin Change ($O(N \cdot \text{Amount})$ Unbounded DP)

*Problem:* Given coins $[1, 2, 5]$, minimum coins to make `amount`.

```python
def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0 # 0 coins to make 0 amount
    
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], 1 + dp[a - c])
                
    return dp[amount] if dp[amount] != float('inf') else -1
```

---

### 5. Master Comparison Matrix

| Problem | Recurrence Relation | Base Case | Space Optimization |
| :--- | :--- | :--- | :--- |
| **Climbing Stairs** | $dp[i] = dp[i-1] + dp[i-2]$ | $dp[0]=1, dp[1]=1$ | 2 Variables ($O(1)$) |
| **House Robber** | $dp[i] = \max(dp[i-1], \text{val} + dp[i-2])$| $dp[0]=\text{nums}[0]$ | 2 Variables ($O(1)$) |
| **Coin Change** | $dp[a] = \min(dp[a], 1 + dp[a - c])$| $dp[0]=0$ | 1D Array of size $\text{amount} + 1$ |

---

### 6. Interview Ke 3 Sawal Is Topic Se

1. **House Robber II (Circular Houses) kaise solve hota hai?** -> Do scenarios run karo: (1) Ignore house 0 (`nums[1:]`), (2) Ignore last house (`nums[:-1]`), aur dono ka maximum answer return karo.
2. **Coin Change 2 (Number of Ways to Make Change) me combination order duplicate hone se kaise rokte hain?** -> Outer loop me coins aur inner loop me amount iterate karke ($O(N \cdot A)$).
3. **Top-Down Memoization vs Bottom-Up Tabulation me kya difference hai?** -> Top-Down recursion + hash map cache use karta hai; Bottom-Up iterative array fill karta hai aur call stack overhead zero karta hai.

---
**Next Topic:** 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort

Loading lesson content...

JavaScript

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track