Climbing Stairs - At most m steps | K5kC

Problem

A person is at the bottom of a staircase with n steps. They can climb up to m steps at a time. The goal is to determine how many unique ways the person can reach the top of the staircase. The number of steps n and the maximum steps they can climb at a time m are given as inputs.

Examples

Example 1

1
2
3
4
5
6


Input:  n = 4, m = 2
Output:  5
Explanation: 
The person can reach the top in the following ways:
1-1-1-1, 1-1-2, 1-2-1, 2-1-1, and 2-2.
Total = 5 ways.

Example 2

1
2
3
4
5
6


Input:  n = 5, m = 3
Output:  13
Explanation: 
The person can reach the top in the following ways:
1-1-1-1-1, 1-1-1-2, 1-1-2-1, 1-2-1-1, 2-1-1-1, 2-2-1, 2-1-2, 1-2-2, 3-1-1, 3-2, 1-3-1, 1-1-3, 3.
Total = 13 ways.

Solution

A person is at the bottom of a staircase with n steps. They can climb up to m steps at a time. The goal is to determine how many unique ways the person can reach the top of the staircase. The number of steps (n) and the maximum steps they can climb at a time (m) are given as inputs.

Method 1 - Naive

Approach

For every step n, calculate the sum of ways to climb n-1, n-2, …, n-m stairs recursively.
Base cases:
- If n == 0, return 1 (standing still).
- If n < 0, return 0 (invalid step).
Return the sum for all possible steps from 1 to m.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#include <iostream>
using namespace std;

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

        // Recursive calculation
        int total = 0;
        for (int i = 1; i <= m; i++) {
            total += countWays(n - i, m);
        }
        return total;
    }
};

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    public int countWays(int n, int m) {
        // Base case
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;
        }

        // Recursive calculation
        int total = 0;
        for (int i = 1; i <= m; i++) {
            total += countWays(n - i, m);
        }
        return total;
    }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def countWays(self, n: int, m: int) -> int:
        # Base cases
        if n == 0:
            return 1
        if n < 0:
            return 0
        
        # Recursive calculation
        total = 0
        for i in range(1, m + 1):
            total += self.countWays(n - i, m)
        
        return total

# Example usage
solution = Solution()
print(solution.countWays(4, 2))  # Output: 5

Complexity

⏰ Time complexity: O(m^n), since all subproblems are repeatedly recomputed.
🧺 Space complexity: O(n) for the recursion call stack.

Dry Run

Lets take the example for m = 4

Steps:

Start at dp[0] = 1 (1 way to climb no stairs).
dp[1] = 1 (only 1 way to climb 1 stair).
dp[2] = dp[1] + dp[0] = 1 + 1 = 2 (ways: [1,1], [2]).
dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4 (ways: [1,1,1], [1,2], [2,1], [3]).
dp[4] = dp[3] + dp[2] + dp[1] + dp[0] = 4 + 2 + 1 + 1 = 8 (ways detailed above).

Thus, the output for m = 4 is 8 ways.

Method 2 - Top-down DP approach

The top-down approach uses memoisation to optimise the naive recursive approach. This method avoids recalculating the solutions for subproblems by storing previously computed results in a dictionary or array.

Approach

Use recursion to calculate the number of ways to climb n stairs by summing ways to climb n-1, n-2, …, n-m stairs.
Use a dictionary (or an array) to store the results of solved subproblems (dp[n]).
Base cases:
- If n == 0, return 1 (standing still).
- If n < 0, return 0 (invalid steps).
Before calculating the result for a subproblem (e.g., dp[n]), check if it has already been computed. If yes, retrieve it from the memoisation table.
Fill the memoisation table as you calculate dp[n].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


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

class Solution {
public:
    int countWays(int n, int m, unordered_map<int, int>& memo) {
        // Base cases
        if (n == 0)
            return 1;
        if (n < 0)
            return 0;

        // Check memoisation table
        if (memo.find(n) != memo.end())
            return memo[n];

        // Recursive calculation with memoisation
        int total = 0;
        for (int i = 1; i <= m; i++) {
            total += countWays(n - i, m, memo);
        }

        memo[n] = total;  // Store result in the memo
        return memo[n];
    }
};

int main() {
    Solution solution;
    unordered_map<int, int> memo;
    cout << solution.countWays(4, 2, memo) << endl;  // Output: 5
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


import java.util.HashMap;

class Solution {
    public int countWays(int n, int m, HashMap<Integer, Integer> memo) {
        // Base cases
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;
        }

        // Check the memoisation table
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // Recursive calculation with memoisation
        int total = 0;
        for (int i = 1; i <= m; i++) {
            total += countWays(n - i, m, memo);
        }

        memo.put(n, total);  // Store result in the memo
        return total;
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        HashMap<Integer, Integer> memo = new HashMap<>();
        System.out.println(solution.countWays(4, 2, memo));  // Output: 5
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def countWays(self, n: int, m: int, memo=None) -> int:
        if memo is None:
            memo = {}
        
        # Base cases
        if n == 0:
            return 1
        if n < 0:
            return 0
        
        # Check memoisation table
        if n in memo:
            return memo[n]
        
        # Recursive calculation with memoisation
        total = 0
        for i in range(1, m + 1):
            total += self.countWays(n - i, m, memo)
        
        memo[n] = total  # Store result in the memo
        return total

# Example usage
solution = Solution()
print(solution.countWays(4, 2))  # Output: 5

Complexity

⏰ Time complexity: O(n * m) because we solve each subproblem for dp[i] at most once, and there are at most m recursive calls for each n.
🧺 Space complexity: O(n) for the recursion stack and memoisation table.

Method 3 - Bottom-up DP approach

This is a variation of the “staircase problem” and can be solved using dynamic programming. The reasoning proceeds as follows:

The problem can be broken down into subproblems: to determine the ways to reach the top of n steps, consider how the person can arrive there using 1, 2, …, or up to m steps.
To determine ways to reach step n, sum up the number of ways to reach steps n-1, n-2, …, n-m.

Base cases:

If n == 0, there’s 1 way (standing still).
For n < 0, there are 0 ways.

Approach

We use dynamic programming because the problem exhibits both overlapping subproblems (repeated computation for the same value of n) and optimal substructure (solution of the larger problem depends on smaller subproblems).

Steps:

Create a dp array where dp[i] represents the number of ways to climb i steps.
Initialise dp[0] = 1 (1 way to stay on ground).
For each step i from 1 to n:
- Calculate dp[i] by summing dp[i-1] to dp[i-m] (only considering valid indices).
Return dp[n].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


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

class Solution {
public:
    int countWays(int n, int m) {
        // Edge case
        if (n == 0)
            return 1;
        
        // Create a DP array to store the number of ways to reach each step
        vector<int> dp(n + 1, 0);
        dp[0] = 1; // Base case: 1 way to stay on ground
        
        // Populate the DP array
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(m, i); j++) {
                dp[i] += dp[i - j];
            }
        }
        
        // Result is in dp[n]
        return dp[n];
    }
};

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    public int countWays(int n, int m) {
        // Edge case
        if (n == 0) 
            return 1;

        // Create a DP array to store the number of ways to reach each step
        int[] dp = new int[n + 1];
        dp[0] = 1; // Base case: 1 way to stay on ground

        // Populate the dp array
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(m, i); j++) {
                dp[i] += dp[i - j];
            }
        }

        // Result is in dp[n]
        return dp[n];
    }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def countWays(self, n: int, m: int) -> int:
        # Edge case
        if n == 0:
            return 1
        
        # Create a DP array to store the number of ways to reach each step
        dp = [0] * (n + 1)
        dp[0] = 1  # Base case: 1 way to stand on ground
        
        # Populate the dp array
        for i in range(1, n + 1):
            for j in range(1, min(m, i) + 1):
                dp[i] += dp[i - j]
        
        # Result is in dp[n]
        return dp[n]

# Example usage
solution = Solution()
print(solution.countWays(4, 2))  # Output: 5

Complexity

⏰ Time complexity: O(n * m) since for each of the n steps, we calculate at most m terms.
🧺 Space complexity: O(n) for storing the dp array.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 - Naive#

Approach#

Code#

Complexity#

Dry Run#

Method 2 - Top-down DP approach#

Approach#

Code#

Complexity#

Method 3 - Bottom-up DP approach#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Solution

Method 1 - Naive

Approach

Code

Complexity

Dry Run

Method 2 - Top-down DP approach

Approach

Code

Complexity

Method 3 - Bottom-up DP approach

Approach

Code

Complexity