Dynamic Programming Basics

# CHAPTER 13

Dynamic Programming Basics #

1. Chapter Introduction #

2. The Core Concept (Why DP exists) #

Dynamic Programming says: "Those who cannot remember the past are condemned to repeat it." If we calculate F(3) once, and save the answer in a Hash Map or Array, the next time the recursion asks for F(3), we instantly return the saved answer. The Time Complexity drops instantly from O(2^N) to O(N).

3. Method 1: Top-Down with Memoization #

*Example: Climbing Stairs (LeetCode 70)* *Prompt:* You are climbing a staircase. It takes n steps. You can climb 1 or 2 steps at a time. How many distinct ways can you climb to the top?

def climbStairs_Memo(n):
    cache = {} # The Memoization dictionary
    
    def dfs(step):
        # Base Cases
        if step == n: return 1
        if step > n: return 0
        
        # Check Cache BEFORE calculating
        if step in cache:
            return cache[step]
            
        # Recursive Relation: Ways to top = (Take 1 step) + (Take 2 steps)
        cache[step] = dfs(step + 1) + dfs(step + 2)
        return cache[step]
        
    return dfs(0)
# Time: O(N), Space: O(N)

4. Method 2: Bottom-Up Tabulation #

def climbStairs_Tabulation(n):
    if n <= 2: return n
    
    dp = [0] * (n + 1) # Create the DP Table
    dp[1] = 1 # Base cases
    dp[2] = 2
    
    for i in range(3, n + 1):
        # State Transition Equation
        dp[i] = dp[i - 1] + dp[i - 2]
        
    return dp[n]
# Time: O(N), Space: O(N)

5. The Ultimate Optimization: Space Reduction #

def climbStairs_Optimized(n):
    if n <= 2: return n
    prev1 = 1
    prev2 = 2
    
    for _ in range(3, n + 1):
        current = prev1 + prev2
        prev1 = prev2
        prev2 = current
        
    return prev2
# Time: O(N), Space: O(1) Constant Space!

6. The 4-Step Framework for Solving DP #

1. 1. Define the State: What parameters define your current situation? (e.g., step_number).

1. 2. Determine the Base Cases: What is the simplest possible input? (e.g., if step == n: return 1).

1. 3. Find the State Transition Equation: How does a state relate to its previous states? (e.g., dp[i] = dp[i-1] + dp[i-2]).

1. 4. Add Memoization/Tabulation: Cache the results.

7. Pattern: 1D Dynamic Programming (House Robber) #

• Option A: Rob this house i + the loot from house i - 2.

• Option B: Do NOT rob this house. Keep the loot from house i - 1.

8. Mini Project: Coin Change #

9. Common Mistakes #

• Off-by-One Array Sizes: When creating a DP table for an integer N, you usually need an array of size N + 1 so that dp[N] is a valid index.

• Skipping the Brute Force: In an interview, explicitly write out the slow recursive tree first. Show the interviewer the repeated work. *Then* add the Memoization dictionary. It proves you understand *why* DP is needed.

10. Best Practices #

• Top-Down First: Top-Down Memoization is usually much more intuitive to write because it follows natural human logic (Recursion). Bottom-up Tabulation requires figuring out the exact loop indices, which can be tricky under pressure. Stick to Memoization unless asked to optimize.

11. Exercises #

1. 1. What is the Space Complexity of the Top-Down Memoized Climbing Stairs algorithm?

1. 2. Write the State Transition equation for the House Robber problem.

12. MCQs #

14. Interview Questions #

• Q: "You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. Find the minimum cost to reach the top of the floor." (LeetCode 746).

15. FAQs #

• Q: Does every recursive function need Dynamic Programming?

16. Summary #

17. Next Chapter Recommendation #