Программа Python для подсчета путей, чтобы добраться до n-й ступени

# Программа для подсчета количества способов добраться до n ступени

  
# Рекурсивная программа для поиска n-го числа Фибоначчи

def fib(n):

    if n <= 1:

        return n

    return fib(n-1) + fib(n-2)

  
# возвращает нет. способов добраться до лестницы

def countWays(s):

    return fib(s + 1)

  
# Драйверная программа

s = 4

print "Number of ways = ",

print countWays(s)

  
# Предоставлено Харшитом Агравалом

# Программа для подсчета количества способов добраться до n ступени

  
# Рекурсивная функция, используемая countWays

def countWaysUtil(n, m):

    if n <= 1:

        return n

    res = 0

    i = 1

    while i<= m and i<= n:

        res = res + countWaysUtil(n-i, m)

        i = i + 1

    return res

      
# Возвращает количество способов добраться до лестницы

def countWays(s, m):

    return countWaysUtil(s + 1, m)

  
# Драйверная программа

s, m = 4, 2

print "Number of ways =", countWays(s, m)

  
# Предоставлено Харшитом Агравалом

# Программа для подсчета количества способов добраться до n ступени

  
# Рекурсивная функция, используемая countWays

def countWaysUtil(n, m):

    res = [0 for x in range(n)] # Создает список со всеми элементами 0

    res[0], res[1] = 1, 1

    for i in range(2, n):

        j = 1

        while j<= m and j<= i:

            res[i] = res[i] + res[i-j]

            j = j + 1 

    return res[n-1]

  
# Возвращает количество способов добраться до лестницы

def countWays(s, m):

    return countWaysUtil(s + 1, m)

      
# Драйверная программа

s, m = 4, 2

print "Number of ways =", countWays(s, m)

      
# Предоставлено Харшитом Агравалом