A child is running up a staircase with n steps and 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 run up the stairs.Examples: Input : 4Output : 7Explanation:Below are the seven ways 1 step + 1 step + 1 step + 1 step 1 step + 2 step + 1 step 2 step + 1 step + 1 step 1 step + 1 step + 2 step 2 step + 2 step 3 step + 1 step 1 step + 3 stepInput : 3Output : 4Explanation:Below are the four ways 1 step + 1 step + 1 step 1 step + 2 step 2 step + 1 step 3 stepNote : print the answer % 10^9+7Constraint:1 <= N <= 10000
Question
A child is running up a staircase with n steps and 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 run up the stairs.Examples: Input : 4Output : 7Explanation:Below are the seven ways 1 step + 1 step + 1 step + 1 step 1 step + 2 step + 1 step 2 step + 1 step + 1 step 1 step + 1 step + 2 step 2 step + 2 step 3 step + 1 step 1 step + 3 stepInput : 3Output : 4Explanation:Below are the four ways 1 step + 1 step + 1 step 1 step + 2 step 2 step + 1 step 3 stepNote : print the answer % 10^9+7Constraint:1 <= N <= 10000
Solution
This problem can be solved using dynamic programming. Here is a Python solution:
def countWays(n):
mod = 1000000007
dp = [0 for i in range(n+1)]
dp[0] = dp[1] = 1
if n>1:
dp[2] = 2
if n>2:
for i in range(3, n+1):
dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % mod
return dp[n]
n = 4
print(countWays(n)) # Output: 7
n = 3
print(countWays(n)) # Output: 4
In this solution, we create an array dp where dp[i] will be storing the number of solutions for value i. We initialize dp[0], dp[1], and `dp[
Similar Questions
Count ways to reach the nth stair
You are climbing a staircase. It takes n steps to reach the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example 1:Input: n = 2Output: 2Explanation: There are two ways to climb to the top.1. 1 step + 1 step2. 2 stepsExample 2:Input: n = 3Output: 3Explanation: There are three ways to climb to the top.1. 1 step + 1 step + 1 step2. 1 step + 2 steps3. 2 steps + 1 step Constraints:1 <= n <= 45
staircase functionLet’s say we have a staircase of N steps, and a person has the ability to climbone, two, or three steps at a time. How many different possible “paths” cansomeone take to reach the top?Base cases: 0 -> 0 1 -> 1 2 -> 2 (1,1),(2) 3 -> 4 (1,1,1),(1,2),(2,1),(3)Test Case 1:Enter steps in staircase: 624Test Case 2:Enter steps in staircase: 20121415Sample Test Cases
Raju is walking down an escalator (a moving staircase) which is moving down. From the top, he takes 20 steps to reach the bottom, while Rajat, who walks twice as fast as Raju, takes 30 steps from the top to reach the bottom.Question No. 11DIRECTIONS for questions 11 and 12: Type in your answer in the input box provided below the question.Find the total number of steps visible at any point of time on the escalator.
You are climbing a staircase. It takes n steps to reach the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Input FormatInput from stdin will be processed as follows and passed to the function.The first line contains an integer n, the number of steps.Constraints0 <= n <= 1000Output FormatThe output is the number of waysSample Input 02Sample Output 02
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.