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