DP Foundations

#Topic: Fibonacci — Simple Recursion, Memoization, @lru_cache
#Time: O(2^n) simple recursion, O(n) memoization
#Space: O(n) common

import sys
import time
from functools import lru_cache

sys.setrecursionlimit(10_000)


#── Method 1: Simple Recursion (Inefficient) ────────────────────────────────────────────
def fib_naive(n: int) -> int:
    """Simple recursive Fibonacci.

    Time:  O(2^n) — Exponential redundant calculations
    Space: O(n)   — Recursion stack"""
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


#── Method 2: Manual Memoization ────────────────────────────────────────────
def fib_memo(n: int, cache: dict[int, int] | None = None) -> int:
    """Memoized Fibonacci.

    Time:  O(n) — Each n is calculated only once
    Space: O(n) — Cache dictionary"""
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]


#── Method 3: @lru_cache Decorator ─────────────────────────────────────────
@lru_cache(maxsize=None)
def fib_lru(n: int) -> int:
    """Automatic memoization using @lru_cache.

    Time:  O(n)
    Space: O(n)"""
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)


#── Method 4: Explicit Memo Table (Class Variable) ─────────────────────────────
_memo: dict[int, int] = {}


def fib_global_memo(n: int) -> int:
    """Global dictionary memoization.

    Time:  O(n) — Across all calls
    Space: O(n)"""
    if n in _memo:
        return _memo[n]
    if n <= 1:
        _memo[n] = n
        return n
    _memo[n] = fib_global_memo(n - 1) + fib_global_memo(n - 2)
    return _memo[n]


#── Performance Comparison ─────────────────────────────────────────────────────────
def benchmark(func, n: int, label: str) -> None:
    start = time.perf_counter()
    result = func(n)
    elapsed = time.perf_counter() - start
    print(f"{label:30s}: fib({n}) = {result}, Time = {elapsed:.6f}s")


if __name__ == "__main__":
    print("=== Fibonacci Result Check ===")
    for i in range(11):
        print(f"  fib({i:2d}) = {fib_lru(i)}", end="")
        if i < 10:
            print(",", end="")
    print()

    print("=== Performance Comparison ===")
    n = 30
    benchmark(fib_naive, n, "Simple Recursion")
    benchmark(lambda x: fib_memo(x), n, "Manual Memoization")
    benchmark(fib_lru, n, "@lru_cache")
    benchmark(fib_global_memo, n, "Global Dictionary")

    print("=== Limits of Simple Recursion ===")
    print(f"fib(35) simple recursion: {fib_naive(35)} (slow...)")
    print(f"fib(35) lru_cache:  {fib_lru(35)} (instant)")

    print("=== @lru_cache Cache Information ===")
    info = fib_lru.cache_info()
    print(f"  hits={info.hits}, misses={info.misses}, size={info.currsize}")

#Topic: Fibonacci Tabulation (Bottom-up) and Space Optimization
#Time: O(n)   Space: O(n) → O(1) Optimization

def fib_tabulation(n: int) -> int:
    """Tabulation Fibonacci (Bottom-up).

    Fill the table in order from the smallest problem.

    Time:  O(n)
    Space: O(n) — dp array"""
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


def fib_space_optimized(n: int) -> int:
    """Space-optimized Fibonacci.

    dp[i] only needs dp[i-1] and dp[i-2] → 2 variables are enough

    Time:  O(n)
    Space: O(1) ← key!"""
    if n <= 1:
        return n

    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr

    return prev1


def fib_generator(count: int):
    """Fibonacci sequence generator.

    Time:  O(1) per yield
    Space: O(1)"""
    a, b = 0, 1
    for _ in range(count):
        yield a
        a, b = b, a + b


def fib_matrix(n: int) -> int:
    """Fibonacci using matrix exponentiation O(log n).

    [[1,1],[1,0]]^n = [[fib(n+1), fib(n)], [fib(n), fib(n-1)]]

    Time:  O(log n)
    Space: O(log n) — recursion stack"""
    if n <= 1:
        return n

    def mat_mul(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
        return [
            [a[0][0]*b[0][0] + a[0][1]*b[1][0],
             a[0][0]*b[0][1] + a[0][1]*b[1][1]],
            [a[1][0]*b[0][0] + a[1][1]*b[1][0],
             a[1][0]*b[0][1] + a[1][1]*b[1][1]],
        ]

    def mat_pow(m: list[list[int]], p: int) -> list[list[int]]:
        if p == 1:
            return m
        if p % 2 == 0:
            half = mat_pow(m, p // 2)
            return mat_mul(half, half)
        return mat_mul(m, mat_pow(m, p - 1))

    base = [[1, 1], [1, 0]]
    result = mat_pow(base, n)
    return result[0][1]


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    print("=== Tabulation vs Space Optimization ===")
    print(f"{'n':>5} | {'Tabulation':>15} | {'Space O(1)':>15} | {'Matrix O(logn)':>15}")
    print("-" * 58)
    for n in [0, 1, 5, 10, 20, 30, 40]:
        t = fib_tabulation(n)
        s = fib_space_optimized(n)
        m = fib_matrix(n)
        print(f"{n:>5} | {t:>15} | {s:>15} | {m:>15}")

    print("\n=== Tabulation Table Visualization (n=10) ===")
    dp = [0] * 11
    dp[1] = 1
    print(f"dp[0] = {dp[0]}")
    print(f"dp[1] = {dp[1]}")
    for i in range(2, 11):
        dp[i] = dp[i-1] + dp[i-2]
        print(f"dp[{i}] = dp[{i-1}] + dp[{i-2}] = {dp[i-1]} + {dp[i-2]} = {dp[i]}")

    print("\n=== Fibonacci Generator (First 15) ===")
    fib_list = list(fib_generator(15))
    print(f"  {fib_list}")

    print("\n=== Space Optimization Process Visualization ===")
    prev2, prev1 = 0, 1
    print(f"Initial: prev2={prev2}, prev1={prev1}")
    for i in range(2, 11):
        curr = prev1 + prev2
        print(f"  i={i}: {prev2} + {prev1} = {curr}")
        prev2, prev1 = prev1, curr
    print(f"Result: {prev1}")

#Topic: Climbing Stairs DP
# Time: O(n)   Space: O(n) → O(1)

def climb_basic(n: int) -> int:
    """Basic Stair Climbing: 1 or 2 steps at a time.

    dp[i] = number of ways to reach step i
    dp[i] = dp[i-1] + dp[i-2]

    Time:  O(n)
    Space: O(n)"""
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1   # {1}
    dp[2] = 2   # {1,1}, {2}

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


def climb_k_steps(n: int, k: int) -> int:
    """Variation: When you can climb up to k steps at a time.

    dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k]

    Time:  O(n × k)
    Space: O(n)"""
    dp = [0] * (n + 1)
    dp[0] = 1   #Step 0 = Starting point

    for i in range(1, n + 1):
        for step in range(1, k + 1):
            if i - step >= 0:
                dp[i] += dp[i - step]

    return dp[n]


def climb_no_consecutive_two(n: int) -> int:
    """Baekjoon 2579 Variation: When you cannot climb 2 steps consecutively twice in a row.

    State: dp[i][j]
      i = current stair number
      j = 0: this stair is the first in a consecutive sequence, j = 1: this stair is the second in a consecutive sequence

    Actual problem 2579 does not allow 3 consecutive steps, so refer to the solution below:

    dp[i][0] = stepping on stair i only once consecutively (jump 2 steps from i-2)
    dp[i][1] = stepping on stair i twice consecutively (jump 1 step from i-1)
    dp[i][0] = dp[i-2][0] + dp[i-2][1]  (including score)
    dp[i][1] = dp[i-1][0]               (including score)

    Time:  O(n)
    Space: O(n)"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2

    #Simple stair count (score-less version)
    dp0 = [0] * (n + 1)  #First in a row
    dp1 = [0] * (n + 1)  #Second in a row

    dp0[1] = 1
    dp1[1] = 0
    if n >= 2:
        dp0[2] = 1
        dp1[2] = 1

    for i in range(3, n + 1):
        dp0[i] = dp0[i - 2] + dp1[i - 2]
        dp1[i] = dp0[i - 1]

    return dp0[n] + dp1[n]


def climb_ways_space_optimized(n: int) -> int:
    """Space-optimized stair climbing.

    Time:  O(n)
    Space: O(1)"""
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    print("=== Basic Stair Climbing (1 step or 2 steps) ===")
    print(f"{'n':>5} | {'Number of ways':>10}")
    print("-" * 20)
    for n in range(1, 11):
        print(f"{n:>5} | {climb_basic(n):>10}")

    print("=== Climbing up to k steps ===")
    n = 10
    for k in [1, 2, 3, 4]:
        print(f"n={n}, k={k}: {climb_k_steps(n, k)} ways")

    print("=== Case enumeration (n=4, 1 step or 2 steps) ===")
    def enumerate_ways(n: int) -> list[list[int]]:
        if n == 0:
            return [[]]
        if n < 0:
            return []
        ways = []
        for step in [1, 2]:
            for rest in enumerate_ways(n - step):
                ways.append([step] + rest)
        return ways

    for n in range(1, 6):
        ways = enumerate_ways(n)
        print(f"n={n}: {len(ways)} ways → {ways[:3]}{'...' if len(ways) > 3 else ''}")

    print("=== Space Optimization ===")
    for n in [5, 10, 20, 50]:
        print(f"  climb({n}) = {climb_ways_space_optimized(n)}")

#Topic: Coin Change — Minimum Number (Greedy Failure), Number of Cases
# Time: O(amount × len(coins))
# Space: O(amount)


def min_coins(coins: list[int], amount: int) -> int:
    """Minimum Coin Count (DP).

    dp[i] = minimum number of coins to make i won
    dp[0] = 0
    dp[i] = min(dp[i - coin] + 1) for coin ≤ i

    Time:  O(amount × len(coins))
    Space: O(amount)"""
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return int(dp[amount]) if dp[amount] != INF else -1


def greedy_coins(coins: list[int], amount: int) -> int:
    """Greedy Coin Change (not always optimal!).

    Time:  O(len(coins) × log(len(coins))) — including sorting
    Space: O(1)"""
    coins_sorted = sorted(coins, reverse=True)
    count = 0
    remaining = amount
    for coin in coins_sorted:
        count += remaining // coin
        remaining %= coin
    return count if remaining == 0 else -1


def count_ways(coins: list[int], amount: int) -> int:
    """Number of ways to make amount with coins (order doesn't matter).

    dp[i] = number of ways to make i won
    Process each coin in order → avoids duplicate permutations

    Time:  O(amount × len(coins))
    Space: O(amount)"""
    dp = [0] * (amount + 1)
    dp[0] = 1   #0 Won: 1 way without using coins

    for coin in coins:           #External: Coin types
        for i in range(coin, amount + 1):   #Internal: Amount
            dp[i] += dp[i - coin]

    return dp[amount]


def count_permutations(coins: list[int], amount: int) -> int:
    """Number of permutations to make amount with coins (order matters).

    dp[i] = number of permutations to make i won
    (outer: amount, inner: coin types)

    Time:  O(amount × len(coins))
    Space: O(amount)"""
    dp = [0] * (amount + 1)
    dp[0] = 1

    for i in range(1, amount + 1):   #External: Amount
        for coin in coins:            #Internal: Coin types
            if coin <= i:
                dp[i] += dp[i - coin]

    return dp[amount]


def reconstruct_coins(coins: list[int], amount: int) -> list[int] | None:
    """Recovering minimum coin combination.

    Time:  O(amount × len(coins))
    Space: O(amount)"""
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0
    parent = [-1] * (amount + 1)   #For Backtracking

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                parent[i] = coin

    if dp[amount] == INF:
        return None

    #Backtracking
    result: list[int] = []
    curr = amount
    while curr > 0:
        coin = parent[curr]
        result.append(coin)
        curr -= coin

    return sorted(result, reverse=True)


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    print("=== Greedy Failure Example ===")
    coins_bad = [1, 5, 6, 9]
    amount = 11
    greedy_ans = greedy_coins(coins_bad, amount)
    dp_ans = min_coins(coins_bad, amount)
    print(f"Coins: {coins_bad}, Amount: {amount}")
    print(f"Greedy: {greedy_ans} coins (9+1+1)")
    print(f"DP:     {dp_ans} coins (5+6)")

    print("=== Korean Coins (Greedy Optimal) ===")
    korean_coins = [500, 100, 50, 10, 5, 1]
    for amount in [1260, 730, 999]:
        g = greedy_coins(korean_coins, amount)
        d = min_coins(korean_coins, amount)
        print(f"{amount} Won: Greedy={g}, DP={d}, {'Match' if g == d else 'Mismatch!'}")

    print("=== Number of Cases (Combination vs Permutation) ===")
    coins = [1, 2, 3]
    for amt in [3, 4, 5]:
        comb = count_ways(coins, amt)
        perm = count_permutations(coins, amt)
        print(f"{amt} Won: Combination={comb}, Permutation={perm}")

    print("=== Minimum Coin Combination Recovery ===")
    test_cases = [(coins_bad, 11), ([1, 2, 5], 11), ([2], 3)]
    for c, a in test_cases:
        combo = reconstruct_coins(c, a)
        print(f"Coins={c}, Amount={a}: {combo}")