Mathematics- NK Ladder

#1

In NK Ladder Problem, where we need to find no of ways to get to nth step by taking 1,2,…k steps.
In Simple Recursion- Recursive case = return F(n-1) + F(n-2) + … + F(n-k) having Base Case- if(n < 0) return 0 and if(n == 0) return 1.

This worked fine, but in video, prateek bhaiya told about more efficient way in which linear recurrence function is reduced to- F(n) = 2*F(n-1) + F(n-(k+1)). But, when implemented using Recursion, it’ll not give right ans. How to use this function for efficient code???

#2

Hi Shashank Sinha, Mention Problem name and link .

#3

Like this, except going just for 3, it can go from 1,2…k steps.

#4

Hey Shashank.
This question can be solved by many ways.For your exact query about Above given equation .Can u mention video link and time stamp.
As I can’t figure out the reason by just Seeing equation.

I can tell u other ways to solve this problem.

  1. Dynamic Programming
  2. Matrix Exponentiation
#5

link- https://online.codingblocks.com/player/17045/content/1005?s=4018
at 13:50

#6

@sanjeetboora Can u pls rectify this as we don’t have access to online material .
Thanx

#7

What you have taken for initial entry b={1,1,2}?
Can you please look into my code why I’m getting the wrong answer?
Code https://ide.codingblocks.com/s/84306