✅ DP

문제

링크

1. 문제 접근 및 해결 로직

마지막 자리에 따라 그 다음 올 수 있는 수들이 다르므로
마지막 수를 저장해가며 길이가 N인 오르막 수의 개수를 구한다.

• 정의
  $f(N,d)$ : 길이가 $N$이면서 마지막 수가 d인 오르막 수의 개수
• 구하는 답
  $sum(f(N,0),f(N,1),...,f(N,9))$
• 초기값
  $f(1,0)=1$
  $f(2,0)=1$
  ...
  $f(N,0)=1$
• 점화식
  $f(N,d)=sum(f(N-1,i)),(0<=i<=d)$

오름차순을 만족해야 하므로 바로 이전의 마지막 숫자 $i$ 는 현재 마지막 숫자 $d$ 를 넘어서는 안된다.

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항