[알고리즘] DP #1

🔗 연관문제 BOJ 9095

정수를 1,2,3의 합으로 나타내기
ex) 4
= 1+1+1+1
= 1+1+2
= 1+2+1
= 2+1+1
= 2+2
= 1+3
= 3+1
➡️ 총 7가지

dp[1] = 1
dp[2] = 2 ➡️ 1+1 / 2
dp[3] = 4 ➡️ 1+1+1 / 1+2 / 2+1 / 3
dp[4] = (dp[3] 조합) + 1 / (dp[2] 조합) + 2 / (dp[1] 조합) +2 = 1+2+4 = 7
➡️ dp[3] 으로 3을 만들 수 있는 모든 경우의 수에 1을 더하면 4를 만들 수 있고 동일한 원리로 dp[2] 에는 2, dp[1] 에는 3만 추가하면 4를 만들 수 있기 때문에 dp[1]+dp[2]+dp[3] 이 dp[4] 의 경우의 수

⭐️ 최종 solution
dp[n] = dp[n-1] + dp[n-2] +dp[n-3] (단, n > 3)