# 피보나치 - Top-Down
def fib_topdown(n, memo={}):
    if n <= 1:
        return n
    if n in memo:           # 이미 계산했으면 바로 반환
        return memo[n]
    memo[n] = fib_topdown(n-1, memo) + fib_topdown(n-2, memo)
    return memo[n]

print(fib_topdown(10))  # 55

# 피보나치 - Bottom-Up
def fib_bottomup(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]

print(fib_bottomup(10))  # 55

코테에서 일반적으로          → Bottom-Up 추천
점화식 관계가 복잡할 때      → Top-Down이 직관적
n이 크거나 재귀 깊이 우려 시 → Bottom-Up

1. dp[i]의 의미를 명확하게 정의한다
   → "dp[i] = i번째 계단까지 올라가는 최대 점수"

2. 마지막 선택(결정)이 무엇인지 생각한다
   → "i번째 계단에 도달하려면 i-1 또는 i-2에서 왔을 것"

3. 그 선택들 중 최적을 고른다
   → dp[i] = max(dp[i-1], dp[i-2]) + score[i]

# dp[i] = i번째 피보나치 수
# dp[i] = dp[i-1] + dp[i-2]

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[1] = 1

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

    return dp[n]

print(fibonacci(10))  # 55

# dp[i] = i를 1로 만드는 최소 연산 횟수
# dp[i] = min(dp[i//3], dp[i//2], dp[i-1]) + 1

def make_one(n):
    dp = [0] * (n + 1)

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + 1      # 무조건 -1 가능

        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i//3] + 1)

        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2] + 1)

    return dp[n]

print(make_one(10))  # 3  (10 → 9 → 3 → 1)

# dp[i] = i번째 계단까지 올라갈 때 최대 점수
# 경우 1: i-1 계단에서 1칸 올라옴 → 연속 2칸이면 i-3에서 왔어야 함
#          dp[i] = dp[i-3] + score[i-1] + score[i]
# 경우 2: i-2 계단에서 2칸 올라옴 (i-1 안 밟음)
#          dp[i] = dp[i-2] + score[i]

def stair(scores):
    n = len(scores)
    if n == 1:
        return scores[0]
    if n == 2:
        return scores[0] + scores[1]

    dp = [0] * n
    dp[0] = scores[0]
    dp[1] = scores[0] + scores[1]
    dp[2] = max(scores[0] + scores[2], scores[1] + scores[2])

    for i in range(3, n):
        # 경우 1: i-1도 밟고 i도 밟음 (i-2는 못 밟음)
        case1 = dp[i-3] + scores[i-1] + scores[i]
        # 경우 2: i-1은 밟지 않고 i만 밟음
        case2 = dp[i-2] + scores[i]
        dp[i] = max(case1, case2)

    return dp[n-1]

scores = [10, 20, 15, 25, 10, 20]
print(stair(scores))  # 75  (10+25+20+20)

# dp[i] = i원을 만드는 최소 동전 수
# dp[i] = min(dp[i - coin] + 1) for coin in coins if i >= coin

def min_coins(n, coins):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0      # 0원은 동전 0개

    for i in range(1, n + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)

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

coins = [1, 5, 10, 25]
print(min_coins(36, coins))   # 3  (25+10+1)
print(min_coins(11, coins))   # 2  (10+1)

# dp[i] = i원을 만드는 방법의 수

def count_coins(n, coins):
    dp = [0] * (n + 1)
    dp[0] = 1   # 0원 만드는 방법: 아무것도 안 쓰는 1가지

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

    return dp[n]

coins = [1, 2, 5]
print(count_coins(5, coins))  # 4
# (1+1+1+1+1), (1+1+1+2), (1+2+2), (5)

✅ DP 적용 조건
   → 최적 부분 구조 + 중복 부분 문제 둘 다 성립

✅ Top-Down vs Bottom-Up
   → Top-Down: 재귀 + 메모이제이션, 직관적
   → Bottom-Up: 반복문 + 테이블, 빠르고 안정적
   → 코테 기본: Bottom-Up 추천

✅ 점화식 도출 순서
   → dp[i]의 의미 정의 → 마지막 선택 분석 → 점화식 작성

✅ 1차원 DP 대표 유형
   → 피보나치: dp[i] = dp[i-1] + dp[i-2]
   → 1로 만들기: dp[i] = min(dp[i//3], dp[i//2], dp[i-1]) + 1
   → 계단: dp[i] = max(dp[i-3]+s[i-1]+s[i], dp[i-2]+s[i])
   → 동전 최소: dp[i] = min(dp[i-coin]+1)
   → 동전 경우수: dp[i] += dp[i-coin]