백준 11057번 오르막 수

문제

문제 출처 : https://www.acmicpc.net/problem/11057

풀이 과정

dp[j][i]= j번째 에서 i 값의 오르막 수

N=1 (1자리 수 일 때)

dp[1][0] ~ dp[1][9]는 모두 1로지정

N>1 (2자리 수 이상일 때)

점화식 dp[j][i]=dp[j-1][0]+…+dp[j-1][i-1] 을 통해 동적계획법으로 구하면된다.

예)

N=3

dp[3][0~9]=55+45+36+28+21+15+10+6+3+1 = 220

C++ 소스코드