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

[{"language":"C++","code":"#include <iostream>\nusing namespace std;\n\nclass Solution {\npublic:\n    int countWays(int n) {\n        // Base cases\n        if (n == 0) return 1;\n        if (n < 0) return 0;\n\n        // Recursive call for 1 step, 2 steps, and 3 steps\n        return countWays(n - 1) +\n            countWays(n - 2) +\n            countWays(n - 3);\n    }\n};\n\n// Example usage\nint main() {\n    Solution solution;\n    cout << solution.countWays(4) << endl;  // Output: 7\n    cout << solution.countWays(5) << endl;  // Output: 13\n    return 0;\n}","lang":"cpp"},{"language":"Java","code":"class Solution {\n    public int countWays(int n) {\n        // Base cases\n        if (n == 0) return 1;\n        if (n < 0) return 0;\n        \n        // Recursive call for 1 step, 2 steps, and 3 steps\n        return countWays(n - 1) +\n            countWays(n - 2) +\n            countWays(n - 3);\n    }\n\n    // Example usage\n    public static void main(String[] args) {\n        Solution solution = new Solution();\n        System.out.println(solution.countWays(4));  // Output: 7\n        System.out.println(solution.countWays(5));  // Output: 13\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def countWays(self, n: int) -> int:\n        # Base cases\n        if n == 0:\n            return 1\n        if n < 0:\n            return 0\n        \n        # Recursive call for 1 step, 2 steps, and 3 steps\n        return (self.countWays(n - 1) +\n                self.countWays(n - 2) +\n                self.countWays(n - 3))\n\n# Example Usage\nsolution = Solution()\nprint(solution.countWays(4))  # Output: 7\nprint(solution.countWays(5))  # Output: 13","lang":"python"}]

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

[{"language":"C++","code":"#include <iostream>\n#include <vector>\nusing namespace std;\n\nclass Solution {\npublic:\n    int countWays(int n) {\n        vector<int> memo(n + 1, -1);\n        return countWaysMemoHelper(n, memo);\n    }\n\nprivate:\n    int countWaysMemoHelper(int n, vector<int>& memo) {\n        // Base cases\n        if (n == 0) return 1;\n        if (n < 0) return 0;\n\n        // If already computed, return cached result\n        if (memo[n] != -1) return memo[n];\n\n        // Calculate and cache result\n        memo[n] = countWaysMemoHelper(n - 1, memo) +\n                countWaysMemoHelper(n - 2, memo) +\n                countWaysMemoHelper(n - 3, memo);\n\n        return memo[n];\n    }\n};\n\n// Example usage\nint main() {\n    Solution solution;\n    cout << solution.countWays(4) << endl;  // Output: 7\n    cout << solution.countWays(5) << endl;  // Output: 13\n    return 0;\n}","lang":"cpp"},{"language":"Java","code":"import java.util.Arrays;\n\nclass Solution {\n    public int countWays(int n) {\n

Related Tags