Ladders Problem

#1

Problem Statement : Count the number of ways to reach the Nth Stair if you can take K steps, for eg if K = 3, we can take 1, 2 and 3 steps.
In this webinar link , in the approach discussed by Prateek Bhaia, of the time complexity O(N) , don’t we have to compute the initial dp elements upto K? It is ok to compute the value if K is small, but what if the K is large for eg K=10?

#2

Can anyone please help me out with this? It’s been a day since I’ve heard from anyone for this.

#3

@raghav6 If the value of K is large, no doubt the code will have to do more number of computations. Note that for this ladder problem with given n and k where n represents the Nth step and k is the maxm steps you can take. You have to compute all the dp elements upto n. The complexity for this problem is O(n * k) since for filling the DP table(array) of size n, to fill each position in the array you check all the k elements before that position . When k is very small compared to n, you can say that your code will take linear time. But when k approaches n then your complexity approaches O(n^2).

Hope this helps :slightly_smiling_face:

1 Like
#4

Okay so the approach discussed in the video was only for the small value of K right? Thank you though :grinning::blush:

#5

Yes, it was for small values of k.