Count the total number ways to reach the nth stair using step 1, 2 or 3 but the step 3 can be taken only once

Question

For any given value N we have to find the number of ways to reach the top while using steps of 1,2 or 3 but we can use 3 steps only once. for example if n=7 then possible ways could be

[1,1,1,1,1,1,1]

[1,1,1,1,1,2]

etc but we cannot have [3,3,1] or [1,3,3]

I have managed to solve the general case without the constraint of using 3 only once with dynamic programming as it forms a sort of fibonacci series

 def countWays(n) : 
    res = [0] * (n + 1) 
    res[0] = 1
    res[1] = 1
    res[2] = 2

    for i in range(3, n + 1) : 
        res[i] = res[i - 1] + res[i - 2] + res[i - 3] 

    return res[n] 

how do I figure out the rest of it?

Answer 1

Let res0[n] be the number of ways to reach n steps without using a 3-step, and let res1[n] be the number of ways to reach n steps after having used a 3-step.

res0[i] and res1[i] are easily calculated from the previous values, in a manner similar to your existing code.

This is an example of a pretty common technique that is often called "graph layering". See, for example: Shortest path in a maze with health loss

Answer 2

Let us first ignore the three steps here. Imagine that we can only use steps of one and two. Then that means that for a given number n. We know that we can solve this with n steps of 1 (one solution), or n-2 steps of 1 and one step of 2 (n-1 solutions); or with n-4 steps of 1 and two steps of 2, which has n-2×n-3/2 solutions, and so on.

The number of ways to do that is related to the Fibonacci sequence. It is clear that the number of ways to construct 0 is one: just the empty list []. It is furthermore clear that the number of ways to construct 1 is one as well: a list [1]. Now we can proof that the number of ways W_n to construct n is the sum of the ways W_n-1 to construct n-1 plus the number of ways W_n-2 to construct n-2. The proof is that we can add a one at the end for each way to construct n-1, and we can add 2 at the end to construct n-2. There are no other options, since otherwise we would introduce duplicates.

The number of ways W_n is thus the same as the Fibonacci number F_n+1 of n+1. We can thus implement a Fibonacci function with caching like:

cache = [0, 1, 1, 2]
def fib(n):
    for i in range(len(cache), n+1):
        cache.append(cache[i-2] + cache[i-1])
    return cache[n]

So now how can we fix this for a given step of three? We can here use a divide and conquer method. We know that if we use a step of three, it means that we have:

1 2 1 … 1 2 3 2 1 2 2 1 2 … 1
\____ ____/   \_______ _____/
     v                v
  sum is m    sum is n-m-3

So we can iterate over m, and each time multiply the number of ways to construct the left part (fib(m+1)) and the right part (fib(n-m-3+1)) we here can range with m from 0 to n-3 (both inclusive):

def count_ways(n):
    total = 0
    for m in range(0, n-2):
        total += fib(m+1) * fib(n-m-2)
    return total + fib(n+1)

or more compact:

def count_ways(n):
    return fib(n+1) + sum(fib(m+1) * fib(n-m-2) for m in range(0, n-2))

This gives us:

>>> count_ways(0)  # ()
1
>>> count_ways(1)  # (1)
1
>>> count_ways(2)  # (2) (1 1)
2
>>> count_ways(3)  # (3) (2 1) (1 2) (1 1 1)
4
>>> count_ways(4)  # (3 1) (1 3) (2 2) (2 1 1) (1 2 1) (1 1 2) (1 1 1 1)
7