문제의 겹치는 하위 문제 식별

• 동적 프로그래밍은 문제를 겹치는 솔루션이 있는 더 작은 하위 문제로 나눌 수 있을 때 효과적!

리스트나 배열에 저장하기

• 하위 문제의 결과를 저장하려면 리스트, 딕셔너리 또는 2D 배열을 사용한다 => 중복 계산이 방지되고 효율성이 향상

상향식 접근 방식

• 가장 작은 하위 문제를 먼저 해결하고 for 루프를 사용하여 최종 솔루션을 구축하자
• 이는 주요 문제에서 시작하여 더 작은 부분으로 나누는 재귀 알고리즘의 하향식 접근 방식과 반대

반복 루프

• 재귀 호출을 중첩된 for 루프로 대체하여 리스트 및 배열을 반복한다. 루프 순서는 하위 문제가 해결되는 순서로!

피보나치를 이용한 예시

재귀 알고리즘

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

동적 프로그래밍

def fib_dp(n):
    if n == 0 or n == 1:
        return n

    memo = [0] * (n + 1)
    memo[0], memo[1] = 0, 1

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

    return memo[n]