Consider climbing stairs. You can take a single stair up, take two stairs up as
ID: 3768262 • Letter: C
Question
Consider climbing stairs. You can take a single stair up, take two stairs up as a single step, or take three stairs up as a single step. How many different ways can you climb the steps taking a single stair, two stairs, or three stairs on each step? For example, if there are three stairs, then you can climb them in four different ways: 3 single stairs, 1 single stair followed by a pair, and a pair of stairs followed by single stair, or all three stairs in a single step. Four stairs can be climbed 7 different ways.
Write a C++ recursive method findNumWays that has an integer parameter that specifies the number of stairs to climb, and returns the number of different ways to climb the stairs using steps that take one, two, or three stairs at a time. You may assume that the number of stairs specified is non-negative. Determine the complexity.
Explanation / Answer
TIME COMPLEXITY: O(n)
#include <iostream>
using namespace std;
int findNumWays(int numberOfSteps);
int main() {
ios::sync_with_stdio(false);
// call function here
}
int findNumWays(int numberOfSteps) {
if (numberOfSteps < 3 && numberOfSteps > 0) {
return numberOfSteps;
}
if (numberOfSteps == 0) {
return 1;
}
return findNumWays(numberOfSteps-1) + findNumWays(numberOfSteps-2) + findNumWays(numberOfSteps-3);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.