동적 프로그래밍의 수학

1. 최적 부분 구조 (Optimal Substructure)
   부분 문제의 최적해 → 전체 문제의 최적해
   예: 최단 경로 — 부분 경로도 최단

2. 중복 부분 문제 (Overlapping Subproblems)
   같은 부분 문제가 여러 번 등장
   예: 피보나치 — fib(5) 계산 중 fib(3) 여러 번

# 재귀 + 캐시 — 풀어 나가면서 계산 결과 저장

def lcs_topdown(s1, s2):
    """최장 공통 부분수열 — 메모이제이션"""
    cache = {}

    def helper(i, j):
        if i == 0 or j == 0:
            return 0
        if (i, j) in cache:
            return cache[(i, j)]

        if s1[i-1] == s2[j-1]:
            cache[(i, j)] = helper(i-1, j-1) + 1
        else:
            cache[(i, j)] = max(helper(i-1, j), helper(i, j-1))
        return cache[(i, j)]

    return helper(len(s1), len(s2))


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

# 작은 문제부터 표 채우며 큰 문제로

def lcs_bottomup(s1, s2):
    m, n = len(s1), len(s2)
    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_bottomup("ABCBDAB", "BDCAB"))  # 4

# N개 물건, 각 무게 wi와 가치 vi
# 배낭 용량 W에서 최대 가치 가져가기
# 점화식: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],                              # 안 가져감
                    dp[i-1][w - weights[i-1]] + values[i-1]  # 가져감
                )
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]


# 예: 4개 물건, 용량 5
weights = [1, 2, 3, 2]
values  = [4, 5, 6, 3]
capacity = 5
print(knapsack(weights, values, capacity))  # 13


# 시간복잡도: O(n × W)
# 공간복잡도: O(n × W) — 1D dp로 줄이면 O(W)

# 동전 [1, 2, 5]로 11원 만드는 최소 동전 수
# 점화식: dp[amount] = min(dp[amount - coin] + 1) for coin in coins

def min_coins(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if a - coin >= 0:
                dp[a] = min(dp[a], dp[a - coin] + 1)

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


print(min_coins([1, 2, 5], 11))  # 3 (5+5+1)
print(min_coins([2], 3))         # -1 (불가능)

# 점화식: dp[i] = max(dp[j] + 1) for j < i if arr[j] < arr[i]

def lis(arr):
    if not arr:
        return 0
    n = len(arr)
    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, 18 또는 2, 3, 7, 101)


# 더 빠른 — 이진 탐색 활용 O(n log n)
import bisect

def lis_fast(arr):
    tails = []
    for x in arr:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)


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

# 두 문자열을 같게 만드는 최소 편집 (삽입/삭제/교체)
# 점화식: 3가지 경우의 최솟값

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 기저: 빈 문자열로 변환 = 길이만큼 삭제/삽입
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j

    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]  # 같으면 그대로
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,    # 삭제
                    dp[i][j-1] + 1,    # 삽입
                    dp[i-1][j-1] + 1,  # 교체
                )

    return dp[m][n]


print(edit_distance("kitten", "sitting"))  # 3
# kitten → sitten (k→s, 교체)
# sitten → sittin (e→i, 교체)
# sittin → sitting (n→ng, 삽입)