Dynamic programming: four classics

from functools import lru_cache

calls = 0
def fib_slow(n):
    global calls; calls += 1
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)

@lru_cache(maxsize=None)
def fib_memo(n):                       # top-down: recursion + cache
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

def fib_table(n):                      # bottom-up: O(1) space
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_slow(25), "slow calls:", calls)
print(fib_memo(25), fib_table(25), fib_table(90))

75025 slow calls: 242785
75025 75025 2880067194370816120

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount      # fewest coins for a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

def max_subarray(xs):              # Kadane
    best = cur = xs[0]
    for x in xs[1:]:
        cur = max(x, cur + x)             # extend, or start fresh
        best = max(best, cur)
    return best

def climb(n):                             # ways to climb 1 or 2 steps
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(min_coins([1, 3, 4], 6), min_coins([1, 2, 5, 10, 20, 50], 88))
print(max_subarray([5, -2, -8, 3, 4, -1, 6, -9]))
print(climb(10))

2 6
12
89