Dynamic Programming Problems

Climbing Steps - Easy

One of the first DP problems I’ve encountered. A good indicator is if the recursive solution simply doesn’t scale well… Solving this recursively is a simple as 2 base cases and a return, but when n grows that becomes a nightmare and you may stack overflow or take eons.

Breakdown

This DP solution requires an array of integers.

• The index of an element represents the number of steps
• The value of an element is the number of ways those steps (the index) can be climbed
• Similar to the FibonacciSequence , each element’s value is the sum of the preceding two. Code:

public int climbStairs(int n) {  
    int[] steps = new int[n + 1];  
    // base cases to facilitate DP  
    steps[0] = 1;  
    steps[1] = 1;  
    for (int i = 2; i <= n; i++) {  
        steps[i] = steps[i - 1] + steps[i - 2];  
    }  
    return steps[n];  
}

I recommend trying out the example n = 4 on paper to get a feel for it.