[백준][다이나믹] 10844 쉬운계단수

쉬운 계단수는 앞에서 선택된 숫자 다음에 올 수 있는 

숫자는 앞숫자-1, 앞숫자+1 이라는 것을 생각하여 해결 할 수 있다. 

자리수가 1일때는 1~9까지 9개가 존재한다. 

자리수가 2일때부터 다음숫자에 0이 나올 수가 있다. 

앞자리가 0, 9일때는 뒤에 1, 8만 올 수 있으므로 하나만 선택가능하다. 

하지만 1~8은 -1 또는 +1 인 숫자가 올 수 있다. 

이를 이용하여 다음과 같이 해결하면 된다. 

memo[length][number] = memo[length-1][number - 1] + memo[length-1][number + 1

이 결과를 MOD 로 나눈 나머지를 저장하면 된다. 

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