• https://galid1.tistory.com/507

---

✅다이나믹 프로그래밍

큰 문제를 작은 문제로 나누어 푸는 문제

• ✍ 분할 정복(divde and conquer) 👉 큰 문제를 해결하기 위해서 단지 작은 문제로 나누어 푸는 방식
• ✍ 다이나믹 프로그래밍 👉 작은 부분 문제들이 반복되는 것을 이용하여 풀어나가는 방법
  • 🥦 다이나믹 프로그래밍을 적용할 수 있는 문제의 조건
    • 1. 작은 문제가 반복하여 일어나는 경우
    • 2. 같은 문제를 구할 때마다 정답이 동일한 경우

📌 다이나믹 프로그래밍 방법

모든 작은 문제들을 한번만 풀어야 한다.

• 정답을 구한 작은 문제를 어딘가에 메모해 놓는다.
• 큰 문제를 풀 떄, 메모한 작은 문제의 정답값을 이용한다.

📌 Memoization

한 번 계산한 작은 문제를 저장한 뒤 다시 사용하는 방법

• list 또는 dict 자료형을 이용한다.

✍ 피보나치 예시

def fibo_memo(n):
    memo[0] = 1
    memo[1] = 1
    
    if n < 2:
        return memo[n]
    for i in range(2, n+1):
        memo[i] = memo[i-2] + memo[i-1]
    return memo[n]

n = 10
memo = [0] * n

✅Bottom-up & Top-down

📌 Bottom-up

작은 문제부터 차근차근 구해나가는 방법

• bottom-up 방식에서 사용되는 결과 저장용 리스트를 dp table이라고 부른다.
• 재귀를 사용하는 top-down 방식보다 반복문을 사용하는 bottom-up 방식을 권장한다.

def fibo_bottom_up(n):
    if n <=1:
        return n
        
    fir = 0
    sec = 1
    for i in range(0, n-1):
        next = fir + sec
        fir = sec
        sec = next
    return next

📌 Top-down

큰 문제를 풀 때, 작은 문제가 아직 풀리지 않은 경우 그제서야 작은 문제를 해결한다.

• 재귀함수로 구현하는 경우가 대부분이다.
• 코드의 가독성이 좋지만 작성하기 어려운 단점이 있다
• Memoization이라는 용어는 top-down 방식에만 국한 된 표현

def fibo_top_down(n):
    if memo[n] > 0:
        return memo[n]
    if n <= 1:
        memo[n] = n
        return memo[n]
    else:
        memo[n] = fibo_top_down(n-1) + fibo_top_down(n-2)
        return memo[n]
memo = [0] * 100

---

✅문제

• 정수 삼각형
• 퇴사

# [퇴사](https://www.acmicpc.net/problem/14501)
"""
특정 일 이후 가장 최적의 스케쥴은 정해져 있다.
예를 들면, 3일차 이후 최대 수익을 구하는 스케쥴은 3일차, 4일차 스케쥴을 선택하는 게 최대 수익을 낼 수 있는 유일한 방법이다.
"""
n = int(input())
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))

dp = [-1] * (n + 1)
dp[n] = 0
for day in reversed(range(n)):
    term, value = data[day]
    if day + term > n:
        dp[day] = max(0, max(dp[day:]))
        continue
    dp[day] = max(max(dp[day:]), value + dp[day + term])

print(max(dp))