[Java] 다이나믹 프로그래밍 (쉬운 계단 수)

이 문제도 dp를 이용하기에 아주 좋은 문제인 것 같다.

 

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

전략은 dp테이블을 2차원 배열로 다음과 같이 생성하는 것!  dp[자릿수][n으로 끝나는 수]

 

배열은 0부터 시작하기 떄문에 dp[1][2]는 자릿수가 2개인 숫자 중에 2로 끝나는 수의 개수를 의미한다.

 

계단 수의 특징은 0과 9로 끝나는 수는 다음 자리수에 1과 8만 올 수 있으므로 해당 케이스는 따로 처리하고,

나머지 숫자들은 자신의 수 보다 +1, -1 한 dp[i][j+1] + dp[i][j-1]로 계산한다.

 

또한 수의 크기가 크므로 자료형을 long으로 지정해주자