DP сверху вниз с мемоизацией

Нисходящий DP: идея мемоизации

# Top-down approach:
# 1. Write the recursive solution (natural but slow)
# 2. Add a memo dict to cache results
# 3. Before recursing, check if the result is cached
# 4. Before returning, store the result in the cache

# This is also called 'memoization' (US spelling)
# 'memoize' means 'to remember', not 'memorize'

# The cache key is the function arguments
# For fib: key is n
# For 2D DP: key is (i, j)
# For 3D DP: key is (i, j, k)
print('Top-down = recursion + memo cache')

Мемоизированные числа Фибоначчи

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]  # return cached result
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Verify speed improvement:
print(fib_memo(30))   # fast!
print(fib_memo(50))   # still fast
print(fib_memo(100))  # no problem

# Without memo, fib_naive(50) would take minutes
# With memo: each of the 50 sub-problems computed once

Использование @functools.lru_cache

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(50))   # 12586269025
print(fib(100))  # works instantly

# Clear cache between tests if needed:
fib.cache_clear()

# Python 3.9+ shorthand:
# from functools import cache
# @cache
# def fib(n): ...

print(fib.cache_info())  # shows hits, misses, maxsize, currsize

Нисходящий DP для размена монет

import functools

def coin_change_top_down(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(remaining):
        if remaining == 0:
            return 0  # no coins needed
        if remaining < 0:
            return float('inf')  # impossible
        # Try each coin and take the minimum
        return 1 + min(dp(remaining - c) for c in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

print(coin_change_top_down([1, 5, 6, 9], 11))  # 2: (5+6) or (2*5+1?no: 9+2?no) 5+6=11 YES
print(coin_change_top_down([2], 3))             # -1: impossible
print(coin_change_top_down([1, 2, 5], 11))      # 3: 5+5+1

Нисходящий DP для подъёма на K шагов

import functools

def climb_k_steps(n, k):
    @functools.lru_cache(maxsize=None)
    def dp(i):
        if i == 0:
            return 1  # base: one way to stay at ground
        if i < 0:
            return 0  # impossible
        # From stair i, you could have come from i-1, i-2, ..., i-k
        return sum(dp(i - j) for j in range(1, k+1) if i - j >= 0)

    return dp(n)

# k=2 (original): should match fib-like sequence
print([climb_k_steps(n, 2) for n in range(7)])  # [1,1,2,3,5,8,13]
# k=3: more options
print([climb_k_steps(n, 3) for n in range(7)])  # [1,1,2,4,7,13,24]

Нисходящий LCS: двумерная мемоизация

import functools

def lcs_top_down(s1, s2):
    m, n = len(s1), len(s2)

    @functools.lru_cache(maxsize=None)
    def dp(i, j):
        if i == 0 or j == 0:
            return 0  # empty prefix has LCS of 0
        if s1[i-1] == s2[j-1]:
            return 1 + dp(i-1, j-1)  # characters match
        return max(dp(i-1, j), dp(i, j-1))  # skip one

    return dp(m, n)

print(lcs_top_down('abcde', 'ace'))   # 3: 'ace'
print(lcs_top_down('abc', 'abc'))     # 3: 'abc'
print(lcs_top_down('abc', 'def'))     # 0: no common chars

Словарь мемоизации или lru_cache: что выбрать

# @lru_cache: clean, automatic, O(1) overhead
# Use when: arguments are simple (int, str, tuple)
import functools
@functools.lru_cache(maxsize=None)
def simple_dp(n):
    if n <= 1: return n
    return simple_dp(n-1) + simple_dp(n-2)

# Manual memo dict: explicit, flexible
# Use when: complex state, need to inspect memo, class methods
def manual_memo_dp(s1, s2):
    memo = {}
    def dp(i, j):
        if (i,j) in memo: return memo[(i,j)]
        if i == 0 or j == 0:
            return 0
        if s1[i-1] == s2[j-1]:
            memo[(i,j)] = 1 + dp(i-1, j-1)
        else:
            memo[(i,j)] = max(dp(i-1,j), dp(i,j-1))
        return memo[(i,j)]
    return dp(len(s1), len(s2))

print(manual_memo_dp('abcde', 'ace'))  # 3

Нисходящий DP для целевой суммы

import functools

def find_target_sum_ways(nums, target):
    @functools.lru_cache(maxsize=None)
    def dp(index, current_sum):
        if index == len(nums):
            return 1 if current_sum == target else 0
        # Try adding the number
        add = dp(index + 1, current_sum + nums[index])
        # Try subtracting the number
        subtract = dp(index + 1, current_sum - nums[index])
        return add + subtract

    return dp(0, 0)

print(find_target_sum_ways([1,1,1,1,1], 3))  # 5
print(find_target_sum_ways([1], 1))            # 1
print(find_target_sum_ways([1], -1))           # 1

Нисходящий и восходящий DP: преимущества и недостатки

# Top-down advantages:
# + Natural: write recursive, add @cache
# + Lazy: only computes needed sub-problems
# + Easy to reason about correctness
# - Uses call stack (recursion limit in Python)
# - Higher constant factor (function call overhead)

# Bottom-up advantages:
# + No recursion limit
# + Better cache performance (sequential memory)
# + Easier to space-optimise (rolling array)
# - Must compute all sub-problems in order
# - Less intuitive for complex 2D/3D problems

# Interview strategy:
# Start with top-down to verify recurrence,
# convert to bottom-up only if asked.
print('Top-down: easy to write | Bottom-up: efficient for large n')

Разбиение строки на слова с нисходящим DP

import functools

def word_break(s, word_dict):
    word_set = set(word_dict)

    @functools.lru_cache(maxsize=None)
    def dp(start):
        if start == len(s):
            return True  # successfully segmented entire string
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and dp(end):
                return True
        return False

    return dp(0)

print(word_break('leetcode', ['leet', 'code']))       # True
print(word_break('applepenapple', ['apple', 'pen'])) # True
print(word_break('catsandog', ['cats', 'dog', 'and', 'cat', 'san', 'andog'])) # False

Предел рекурсии и инструменты итерации

import sys

print('Default recursion limit:', sys.getrecursionlimit())  # 1000

# For large DP problems, increase if needed:
# sys.setrecursionlimit(100000)

# Better: convert to bottom-up DP for large n
def fib_bottom_up(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

# No recursion limit issue:
print(fib_bottom_up(10000))  # works fine, no recursion

Быстрая проверка

Итоги урока