@Lupe... I did not even notice the constant running time condition at first ;)

Frage zur Aufgabe

Stairs

Java Collections, Level 9, Lektion 9

In der Diskussion

So I'd say that's your task and cause of your suggestions I already know how to solve it 😁

A boy runs up a flight of stairs consisting of n steps; in 1 bound, he can move up one, two or three steps.

Implement the numberOfPossibleAscents(int n) method, which should return the number of ways the boy can ascend an entire flight of stairs consisting of n steps.

P.S. If the flight of stairs consists of 0 steps, the method should return 1. For n < 0, return 0.

Anforderungen:

The numberOfPossibleAscents method should return the number of ways to ascend a flight of stairs consisting of n steps.
The numberOfPossibleAscents method should return 1 for n = 0.
The numberOfPossibleAscents method should return 0 for n < 0.
The numberOfPossibleAscents method must have linear running time.

package com.codegym.task.task39.task3904; import java.util.Arrays; /* Stairs */ public class Solution { private static int n = 70; public static void main(String[] args) { System.out.println("The number of possible ascents for " + n + " steps is: " + numberOfPossibleAscents(n)); } public static long numberOfPossibleAscents(int n) { if (n == 0) return 1; if (n < 0) return 0; long result = 0; result += numberOfPossibleAscents (n - 3); result += numberOfPossibleAscents (n - 2); result += numberOfPossibleAscents (n - 1); return result; } }

Kommentare (4)

Beliebt
Neu
Alt

Du musst angemeldet sein, um einen Kommentar schreiben zu können

Guadalupe Gagnon

Level 37 , Tampa, United States

9 Februar 2022, 14:38

Have you watched the video on dynamic programming I shared in this forum post? This problem looks like it can be solved with the techniques in that video. The logic that I have in my head would be to: First pre check N to ensure it is greater than 1, if not either return 0 if its less than 0 otherwise 1. Next create a number array with N + 1 indices. You would set index zero and index one both to 1 and then each subsequent index would be the sum of all previous indices. When complete the last index will contain the correct answer. A int may be too small to contain the max value with an N of 70. I haven't tested the max so idk, but for safety you could write it with a BigInteger, and if the result with N of 70 can be held in an int or long then refactor it.

Guadalupe Gagnon

Level 37 , Tampa, United States

9 Februar 2022, 14:46

That one video is probably the best video I have personally watched and profoundly impacted the way I approach problem solving. Even though it is 5 hours long, it is worth it and I can't recommend it enough.

Lisa

Level 41

9 Februar 2022, 14:56

Hell yes, of course I've seen that video. That's why I said this is your task ;) And that's why I was able to solve it in not even 5 mins, hihihi. I just thought you'd be pleased to see that a dynamic programming task still is in CGs pipe. Despite the need for caching there were no dirty tricks from CGs side. The long return type of their predefined method was sufficient. I even used a static cache array and did not take it with me inside the recursive methods arguments. So I have to say they were very kind with that tasks validation rules. Oh... you just can not use the default array element value cause that is one of the possible return values (if n < 0). So you need to initialize to some neg value or use a list and check for null.

Guadalupe Gagnon

Level 37 , Tampa, United States

9 Februar 2022, 14:57

☺️