The Dynamic Programming Methodology

Effective dynamic programming solutions follow a systematic five-step process:

1. Define the DP array: Establish what each element represents and the meaning of its indices.
2. Formulate the recurrence relation: Identify how current states derive from previous states.
3. Initialize base cases: Set the starting values that seed the computation.
4. Determine iteration order: Establish the sequence for computing values based on dependencies.
5. Validate with examples: Trace through small inputs to verify correctness.

Fibonacci Numbers

The Fibonacci sequence begins with 0 and 1, where each subsequent number equals the sum of the two preceding ones. Given an integer $n$, calculate $F(n)$.

Examples:

• Input: $n = 2$ → Output: 1 ($F(2) = F(1) + F(0) = 1 + 0$)
• Input: $n = 4$ → Output: 3 ($F(4) = F(3) + F(2) = 2 + 1$)

Solution Approach:

Rather than using recursion with memoization or a full array allocation, observe that each calculation only requires the two previous values. This allows an iterative approach with constant space complexity.

The recurrence relation remains $F(n) = F(n-1) + F(n-2)$, with base cases $F(0) = 0$ and $F(1) = 1$.

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        
        int prev2 = 0;  // Represents F(i-2)
        int prev1 = 1;  // Represents F(i-1)
        int current = 0;
        
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
}

Climbing Stairs

You are climbing a staircase with $n$ steps to reach the top. Each move allows climbing either 1 or 2 steps. Determine the number of distinct ways to reach the top.

Examples:

• Input: $n = 2$ → Output: 2 (1+1 steps, or 2 steps at once)
• Input: $n = 3$ → Output: 3 (1+1+1, 1+2, 2+1)

Pattern Recognition:

For the $i$-th step, you could arrive from step $i-1$ (taking a single step) or from step $i-2$ (taking a double step). Therefore, the total ways to reach step $i$ equals the sum of ways to reach steps $i-1$ and $i-2$.

This yields the identical recurrence relation as the Fibonacci sequence: $ways[i] = ways[i-1] + ways[i-2]$, with initial conditions $ways[1] = 1$ and $ways[2] = 2$.

Optimized Implementation:

Instead of maintaining a complete array, track only the last two states:

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int twoBack = 1;  // Ways to reach step i-2
        int oneBack = 2;  // Ways to reach step i-1
        int total = 0;
        
        for (int step = 3; step <= n; step++) {
            total = oneBack + twoBack;
            twoBack = oneBack;
            oneBack = total;
        }
        
        return oneBack;
    }
}

Execution Trace for $n = 5$:

Initial state: twoBack = 1 (step 1), oneBack = 2 (step 2)

• Step 3: total = 2 + 1 = 3, update pointers (twoBack = 2, oneBack = 3)
• Step 4: total = 3 + 2 = 5, update pointers (twoBack = 3, oneBack = 5)
• Step 5: total = 5 + 3 = 8, update pointers (twoBack = 5, oneBack = 8)

Final result: 8 distinct paths.