Динамическое программирование решение, чтобы "подниматься по лестнице"


Это и есть "подъем по лестнице" проблема от leetcode.com:

Вы поднимаетесь на лестницу. Он принимает \ФП\$ шагов, чтобы добраться до вершины.

Каждый раз, когда вы можете подняться еще на 1 или 2 шага. Сколькими различными способами вы можете подняться на вершину?

Примечание: учитывая \н $\$ будет положительным целым числом.

Пример 1:

Вход: 2 Выход: 2 объяснение: есть два способа подняться на топ.

  1. 1 Шаг + 1 шаг
  2. 2 шага

Пример 2:

Входные данные: 3 выходные данные: 3 объяснение: существует три способа подняться на топ.

  1. 1 Шаг + 1 Шаг + 1 шаг
  2. 1 Шаг + 2 шага
  3. 2 шага + 1 шаг

Я думал, что этот вопрос очень похож на вопрос Фибоначчи. Я использую динамическое программирование,

dp[n] = dp[n - 1] + dp[n - 2]



class Solution:
    # @param n, an integer
    # @return an integer
    def climbStairs(self, n):
        dp = [1 for i in range(n+1)]
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]


Комментарии
2 ответа

Код в пост, чтобы вычислить \$я$е число Фибоначчи, \$F_i\$, за каждый \$я \Ле Н\ долл., для того, чтобы вычислить \$F_n\$. Это можно сделать намного лучше, чем то, с помощью повторения $$ \eqalign{F_{2П−1} &= F_{н}^2 + F_{П−1}^2 \\ F_{2Н} &= (2F_{П−1} + F_{Н}) F_{н}} $$ в сочетании с мемоизацией. Например, вы могли бы использовать @functools.lru_cache декоратор, как это:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
"""Return the nth Fibonacci number."""
if n <= 1:
return n
elif n % 2:
a = fibonacci(n // 2)
b = fibonacci(n // 2 + 1)
return a * a + b * b
else:
a = fibonacci(n // 2 - 1)
b = fibonacci(n // 2)
return (2 * a + b) * b

это вычисляет \$10^6\$му числу Фибоначчи, которая имеет более чем 200 000 десятичных цифр, на доли секунды:

>>> from timeit import timeit
>>> timeit(lambda:fibonacci(10**6), number=1)
0.06556476117111742
>>> len(str(fibonacci(10**6)))
208988

Наоборот, код в посте не может вычислить Solution().climbStairs(10 ** 6) без запуска из памяти.

6
ответ дан 30 января 2018 в 02:01 Источник Поделиться

Насколько я понял, динамическое программирование использует мемоизацию, и calculatig вещи при необходимости.

Ваш алгоритм вычисляет все n значения все время, пока тестирование код создает экземпляр класса, а запросы его несколько раз. Ю. можете использовать что-то вроде этого:

def climb_stairs_gen():
a, b = 1, 2
while True:
yield a
a, b = b, a + b

Это генератор, который дает постоянно растущего значения уже по лестнице. Вы используете его в классе такой

from itertools import islice
class Solution:
def __init__(self):
self.values = []
self.generator = climb_stairs_gen()

def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
val = self.values
l = len(val)
if n > l:
val.extend(islice(self.generator, n - l))
return val[n - 1]

Он проверяет, есть ли лестница длиной n или больше рассчитывается уже. Если нет, то это расширяет список с предварительно вычисленными значениями, то возвращается результат для лестницы с длиной n

1
ответ дан 30 января 2018 в 11:01 Источник Поделиться