Wednesday, September 1, 2021

Dynamic Programming - count-ways-reach-nth-stair-using-steps 1-4

Dynamic programming exercise to count number of ways to reach n steps using either n+1 or n+4 steps. Had to use count global variable, as returning r was not giving me the correct answer. This works as expected. 

Recursive algorithm - solve(n - 1) + solve(n - 4)

Python code sample:

count = 0

def solve(n):

  global count 

  # Base case

  if n < 0:

    return 0

  if n == 0:

    return 1

  if n == 1:

      count = count + 1

      return 1

  r = solve(n - 1) + solve(n - 4)

  return r   

# Driver program to test above function

n = 6

ret = solve(n)

print("Final:", count)

Output of this program is 3.



Example: for n = 6 there are 3 ways to get from stairs 1 to stairs 6.
Those are:
1 → 2 → 3 → 4 → 5 → 6,
1 → 2 → 6, and
1 → 5 → 6

No comments:

Post a Comment