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
