동적계획법

동적계획법이란?

• 큰 문제를 작은 단위로 쪼개서 푸는 법
• 점화식을 사용한다. dy[n] = dy[n-1]+3 이런 식으로 재귀적으로 전체 문제를 푼다
• 대표적인 문제로 피보나치 수열, 배낭 문제 등이 있음

예시 문제

계단을 오를 때 한 계단 또는 두 계단 씩 오른다면 N계단을 오를 때 방법의 수는?

1. 도착점을 가장 적은 수부터 정하고 풀어본다.

• 도착점이 1일 경우, 1가지
• 도착점이 2일 경우, 2가지

2. 점화식 도출을 위해 계속해본다.

• 도착점이 3일 경우에는 시작점이 1아니면 2 -> 1 + 2가지
• 도착점이 4일 경우에는 시작점이 2아니면 3 -> 2 + 2가지

출처 : https://wooder2050.medium.com/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95-dynamic-programming-%EC%A0%95%EB%A6%AC-58e1dbcb80a0