Count ways to reach nth stair¶

• https://www.codingninjas.com/codestudio/problems/count-ways-to-reach-nth-stairs_798650

In [6]:

def nth_stair(n):

    # given that we always start from 0th stair
    start_stair = 0

    def solve(n):

        # 1. base case
        # this is invalid, as per the problem statement
        # we cannot have a stair less than 0
        if n < 0:
            return 0
        # If you are on stair 0, then the # ways to reach
        # the 0th stair is 1
        if n == 0:
            return 1

        # recursive relation
        # for counting the remaining ways
        total_ways = solve(n - 1) + solve(n - 2)
        return total_ways

    ans = solve(n)
    return ans

def nth_stair(n): # given that we always start from 0th stair start_stair = 0 def solve(n): # 1. base case # this is invalid, as per the problem statement # we cannot have a stair less than 0 if n < 0: return 0 # If you are on stair 0, then the # ways to reach # the 0th stair is 1 if n == 0: return 1 # recursive relation # for counting the remaining ways total_ways = solve(n - 1) + solve(n - 2) return total_ways ans = solve(n) return ans

In [5]:

nth_stair(5)

nth_stair(5)

Out[5]:

8

In [7]:

def nth_stair_memo(n):

    # 1. create a dp array
    dp = [-1] * (n + 1)

    def solve(n):

        if n < 0:
            return 0

        if n == 0:
            return 1

        # 3. if some intermediate
        # result is already in the dp array
        # return it
        if dp[n] != -1:
            return dp[n]

        # 2. store result in the dp array
        dp[n] = solve(n - 1) + solve(n - 2)

        return dp[n]

    ans = solve(n)

    return ans

def nth_stair_memo(n): # 1. create a dp array dp = [-1] * (n + 1) def solve(n): if n < 0: return 0 if n == 0: return 1 # 3. if some intermediate # result is already in the dp array # return it if dp[n] != -1: return dp[n] # 2. store result in the dp array dp[n] = solve(n - 1) + solve(n - 2) return dp[n] ans = solve(n) return ans

In [16]:

nth_stair_memo(8)

nth_stair_memo(8)

Out[16]:

34

In [17]:

def count_ways(n_stairs):
    # in this case we are building our solution from bottom to top
    start_stair = 0
    # step-1: creation of dp array
    dp = [-1] * (n_stairs + 1)

    def solve(n_stairs, current_stair, dp):

        # base case
        if current_stair == n_stairs:
            return 1

        # if my current stair has exceeded
        # the my n_stair or I have overstepped
        if current_stair > n_stairs:
            return 0

        # step-3: check if the value needed to be computed is already present in the dp array
        if dp[current_stair] != -1:
            return dp[current_stair]

        # step-2: recursive case
        dp[current_stair] = solve(n_stairs, current_stair + 1) + solve(
            n_stairs, current_stair + 2
        )

        # recursive relation
        return dp[current_stair]

    ans = solve(n_stairs=n_stairs, current_stair=start_stair)

    return ans

def count_ways(n_stairs): # in this case we are building our solution from bottom to top start_stair = 0 # step-1: creation of dp array dp = [-1] * (n_stairs + 1) def solve(n_stairs, current_stair, dp): # base case if current_stair == n_stairs: return 1 # if my current stair has exceeded # the my n_stair or I have overstepped if current_stair > n_stairs: return 0 # step-3: check if the value needed to be computed is already present in the dp array if dp[current_stair] != -1: return dp[current_stair] # step-2: recursive case dp[current_stair] = solve(n_stairs, current_stair + 1) + solve( n_stairs, current_stair + 2 ) # recursive relation return dp[current_stair] ans = solve(n_stairs=n_stairs, current_stair=start_stair) return ans

In [18]:

n = 49
ans = count_ways(n)
print(ans)

n = 49 ans = count_ways(n) print(ans)

12586269025