Динамическое программирование

Динамическое программирование (ДП) применяют, когда задача распадается на перекрывающиеся подзадачи. Результаты подзадач сохраняются (мемоизация сверху вниз или таблица снизу вверх), чтобы не считать их заново.

Сложность: зависит от числа состояний и перехода; часто O(n) или O(n·m). Память: O(числа состояний), нередко её можно ужать до O(одного слоя таблицы).

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

print(fib(10))  # 55