Ways to Reach the n'th Stair

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Climb 1 or 2 stairs at a time. dp[n] = dp[n-1] + dp[n-2]. Fibonacci sequence with dp[1]=1, dp[2]=2.

Algorithm

1dp[0]=1, dp[1]=1. dp[i] = dp[i-1] + dp[i-2].

Common Pitfalls

•Base cases: 0 stairs = 1 way (empty), 1 stair = 1 way, 2 stairs = 2 ways. Can also generalize to k steps.

Ways to Reach the n'th Stair.java

Java

// Approach: DP. dp[i] = dp[i-1] + dp[i-2] (can take 1 or 2 steps). Base: dp[0]=dp[1]=1.
// Time: O(n) Space: O(1)
class Solution {
    int countWays(int n) {
        int dp[] = new int[n + 1];
        
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] += dp[i - 1];
            if (i > 1)
                dp[i] += dp[i - 2];
        }

        return dp[n];
    }
}

Was this solution helpful?