동적 프로그래밍(Dynamic Programming)이란 무엇이며 메모이제이션과 타뷸레이션의 차이는?

# 순수 재귀 - O(2ⁿ)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# 메모이제이션 적용 - O(n)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]  # 이미 계산된 값 반환
    if n <= 1:
        return n

    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Python functools.lru_cache 활용
from functools import lru_cache

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

print(fib_cached(100))  # 354224848179261915075 (즉시 계산!)

def fib_tabulation(n):
    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]

# dp 테이블 (n=7):
# dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5, dp[6]=8, dp[7]=13

# 공간 최적화: O(n) → O(1)
def fib_optimized(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

def knapsack(weights, values, capacity):
    """
    weights: 각 물건의 무게
    values:  각 물건의 가치
    capacity: 배낭의 최대 무게
    """
    n = len(weights)
    # dp[i][w] = i번째 물건까지 고려했을 때 무게 w 이하로 담을 수 있는 최대 가치
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 현재 물건을 담지 않는 경우
            dp[i][w] = dp[i-1][w]

            # 현재 물건을 담는 경우 (무게가 허용될 때)
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][capacity]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
capacity = 8
print(knapsack(weights, values, capacity))  # 10

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    # dp[i][j] = s1[:i]와 s2[:j]의 LCS 길이
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # 문자 일치
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # 최대 선택

    return dp[m][n]

print(lcs("ABCBDAB", "BDCAB"))  # 4 (BCAB 또는 BDAB)

def coin_change(coins, amount):
    """최소 동전 개수로 amount 만들기"""
    # dp[i] = 금액 i를 만들기 위한 최소 동전 수
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 금액 0은 동전 0개

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

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

coins = [1, 5, 10, 25]
print(coin_change(coins, 41))  # 4 (25+10+5+1)

def lis(arr):
    """Longest Increasing Subsequence"""
    n = len(arr)
    # dp[i] = arr[i]로 끝나는 LIS의 길이
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 (2,3,7,101 또는 2,5,7,101)

# 격자 경로 수 세기 - 두 방식 비교
# m×n 격자에서 왼쪽 위 → 오른쪽 아래로 가는 경우의 수 (오른쪽/아래로만 이동)

# 메모이제이션 방식 (Top-down)
def unique_paths_memo(m, n, memo={}):
    if (m, n) in memo:
        return memo[(m, n)]
    if m == 1 or n == 1:
        return 1

    result = unique_paths_memo(m-1, n, memo) + unique_paths_memo(m, n-1, memo)
    memo[(m, n)] = result
    return result

# 타뷸레이션 방식 (Bottom-up)
def unique_paths_tab(m, n):
    dp = [[1] * n for _ in range(m)]

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

    return dp[m-1][n-1]

print(unique_paths_memo(3, 7))  # 28
print(unique_paths_tab(3, 7))   # 28