Climbing Stairs - Take atmost 3 steps

Problem

A child is climbing up a staircase with n steps. At each instance, the child can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can jump up the stairs.

Examples

Example 1:

 Input: n = 4  
 Output: 7  
 Explanation: The possible ways are:   
 1. 1 + 1 + 1 + 1  
 2. 1 + 1 + 2  
 3. 1 + 2 + 1  
 4. 2 + 1 + 1  
 5. 2 + 2  
 6. 1 + 3  
 7. 3 + 1

Solution

Method 1 - Recursion

• To climb n steps, the child has three choices at each step: hopping 1 step, 2 steps, or 3 steps.

• If the child takes 1 step, the problem reduces to finding the number of ways to climb n-1 steps.

• Similarly, taking 2 steps reduces the problem to solving for n-2 steps.

• Taking 3 steps reduces the problem to finding the number of ways to climb n-3 steps.

• Thus, the total number of ways to climb n steps is the sum of the ways to climb (n-1) steps, (n-2) steps, and (n-3) steps.

• The naive approach uses plain recursion to compute this directly from the recurrence relation.

• The child can reach the nth step by hopping:

  1. 1 step from (n - 1)
  2. 2 steps from (n - 2)
  3. 3 steps from (n - 3)

Hence, the recurrence relation is:

ways(n) = ways(n - 1) + ways(n - 2) + ways(n - 3)

Base cases:

• ways(0) = 1 (1 way to stay on the ground, i.e., doing nothing)
• ways(1) = 1 (1 way to climb 1 step)
• ways(2) = 2 (2 ways: [1 + 1, 2])

Pseudocode

The simplest approach uses plain recursion, directly following the recurrence relation:

public int possibleWays(int n) {
	if (n<1) {
		return 0;
	}
	return 1 + possibleWays(n - 1) + possibleWays(n - 2) +
		possibleWays(n - 3);
}

Code

C++

#include <iostream>
using namespace std;

class Solution {
public:
    int countWays(int n) {
        // Base cases
        if (n == 0) return 1;
        if (n < 0) return 0;

        // Recursive call for 1 step, 2 steps, and 3 steps
        return countWays(n - 1) +
            countWays(n - 2) +
            countWays(n - 3);
    }
};

// Example usage
int main() {
    Solution solution;
    cout << solution.countWays(4) << endl;  // Output: 7
    cout << solution.countWays(5) << endl;  // Output: 13
    return 0;
}

Java

class Solution {
    public int countWays(int n) {
        // Base cases
        if (n == 0) return 1;
        if (n < 0) return 0;
        
        // Recursive call for 1 step, 2 steps, and 3 steps
        return countWays(n - 1) +
            countWays(n - 2) +
            countWays(n - 3);
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countWays(4));  // Output: 7
        System.out.println(solution.countWays(5));  // Output: 13
    }
}

Python

class Solution:
    def countWays(self, n: int) -> int:
        # Base cases
        if n == 0:
            return 1
        if n < 0:
            return 0
        
        # Recursive call for 1 step, 2 steps, and 3 steps
        return (self.countWays(n - 1) +
                self.countWays(n - 2) +
                self.countWays(n - 3))

# Example Usage
solution = Solution()
print(solution.countWays(4))  # Output: 7
print(solution.countWays(5))  # Output: 13

Complexity

• ⏰ Time complexity: O(3^n) due to exponential recursive calls.
• 🧺 Space complexity: O(n) for the function call stack.

Method 2 - Top-down DP

To optimise the recursive solution and avoid redundant calculations, we'll use memoisation with an array.

Code

C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int countWays(int n) {
        vector<int> memo(n + 1, -1);
        return countWaysMemoHelper(n, memo);
    }

private:
    int countWaysMemoHelper(int n, vector<int>& memo) {
        // Base cases
        if (n == 0) return 1;
        if (n < 0) return 0;

        // If already computed, return cached result
        if (memo[n] != -1) return memo[n];

        // Calculate and cache result
        memo[n] = countWaysMemoHelper(n - 1, memo) +
                countWaysMemoHelper(n - 2, memo) +
                countWaysMemoHelper(n - 3, memo);

        return memo[n];
    }
};

// Example usage
int main() {
    Solution solution;
    cout << solution.countWays(4) << endl;  // Output: 7
    cout << solution.countWays(5) << endl;  // Output: 13
    return 0;
}

Java

import java.util.Arrays;

class Solution {
    public int countWays(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return countWaysMemoHelper(n, memo);
    }

    private int countWaysMemoHelper(int n, int[] memo) {
        // Base cases
        if (n == 0) return 1;
        if (n < 0) return 0;
        
        // If already computed, return the cached result
        if (memo[n] != -1) return memo[n];

        // Calculate and store in memo table
        memo[n] = countWaysMemoHelper(n - 1, memo) +
                countWaysMemoHelper(n - 2, memo) +
                countWaysMemoHelper(n - 3, memo);

        return memo[n];
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countWays(4));  // Output: 7
        System.out.println(solution.countWays(5));  // Output: 13
    }
}

Python

class Solution:
    def countWays(self, n: int, memo: list = None) -> int:
        if memo is None:
            memo = [-1] * (n + 1)
        
        # Base cases
        if n == 0:
            return 1
        if n < 0:
            return 0
        
        # If already computed, return the cached result
        if memo[n] != -1:
            return memo[n]

        # Calculate and store in memo table
        memo[n] = (self.countWays(n - 1, memo) +
                self.countWays(n - 2, memo) +
                self.countWays(n - 3, memo))
        
        return memo[n]

# Example Usage
solution = Solution()
print(solution.countWays(4))  # Output: 7
print(solution.countWays(5))  # Output: 13

Complexity

• ⏰ Time complexity: O(n) since each state n is computed only once.
• 🧺 Space complexity: O(n) for the memoisation array and O(n) for the recursion stack.

Method 3 - Bottom-up DP

We can create a DP array (or variables) to store the number of ways for each stair count up to n and use the recurrence relation to fill the dp array iteratively.

Code

C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int countWays(int n) {
        // Base cases
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;

        // Dynamic programming array
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        // Bottom-up calculation
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        return dp[n];
    }
};

// Example usage
int main() {
    Solution solution;
    cout << solution.countWays(4) << endl;  // Output: 7
    cout << solution.countWays(5) << endl;  // Output: 13
    return 0;
}

Java

class Solution {
    public int countWays(int n) {
        // Base cases
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        // Dynamic programming array
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        // Bottom-up calculation
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        
        return dp[n];
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countWays(4));  // Output: 7
        System.out.println(solution.countWays(5));  // Output: 13
    }
}

Python

class Solution:
    def countWays(self, n: int) -> int:
        # Base cases
        if n == 0:
            return 1
        if n == 1:
            return 1
        if n == 2:
            return 2

        # Dynamic programming array
        dp = [0] * (n + 1)
        dp[0], dp[1], dp[2] = 1, 1, 2

        # Bottom-up calculation
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        
        return dp[n]

# Example Usage
solution = Solution()
print(solution.countWays(4))  # Output: 7
print(solution.countWays(5))  # Output: 13

Complexity

• ⏰ Time complexity: O(n). The solution iterates from 0 to n. For each step, it performs constant-time operations.
• 🧺 Space complexity: O(n). Storing results in an array requires space proportional to n.