동적 계획법(DP)은 컴퓨터 프로그래밍에서 최적화 문제를 해결하기 위한 알고리즘이다. 동적 계획법은 부분 문제들을 풀고, 그 해답을 저장함으로써 전체 문제를 해결하는 방식이다.
예를 들어, 피보나치 수열을 계산하는 문제에서 동적 계획법을 사용할 수 있다. 피보나치 수열은 다음과 같이 정의된다.
$F(n) = \begin{cases} 0 &\text{if } n = 0 \\ 1 &\text{if } n = 1 \\ F(n-1) + F(n-2) &\text{if } n > 1 \end{cases}$
이를 재귀적으로 구현하면 다음과 같이 나온다.
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
하지만 이 코드는 n이 커질수록 $O(2^N)$ 으로 느려진다. 이를 해결하기 위해 동적 계획법을 사용할 수 있다. 동적 계획법을 사용하면 중복되는 부분 문제들을 피해 전체 문제를 해결하는 데 필요한 계산을 줄일 수 있다.
예를 들어, 다음과 같이 동적 계획법을 사용하여 피보나치 수열을 구할 수 있다.
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
fib = [0, 1]
for i in range(2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
이 코드는 $O(n)$ 시간 내에 피보나치 수열을 계산할 수 있다.
예시 1에서 다루는 계단 오르기 문제는 동적 계획법(Dynamic Programming)의 대표적인 예시 중 하나이다. 계단 오르기 문제는 n개의 계단을 오를 때, 1개 또는 2개의 계단씩 오를 수 있을 때, 계단을 오르는 방법의 수를 구하는 문제이다.
예를 들어, 3개의 계단을 오르는 방법은 다음과 같이 3가지가 있다.
이 문제를 동적 계획법으로 해결하면, n-1번째 계단에서 1개의 계단을 오르거나, n-2번째 계단에서 2개의 계단을 오르는 방법을 더한 값이 n번째 계단을 오르는 방법의 수가 된다.
아래 코드는 위와 같은 방법으로 계단 오르기 문제를 해결하는 동적 계획법 코드이다.
def climbStairs(n: int) -> int:
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
위 코드에서,