문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.해설 인접한 모든 자리의 차이가 '1'인 수를 계단 수라고 할 때, 길이 N ( 1 다이나믹 프로그래밍으로 문제에 접근해야 한다. DP 문제의 핵심은 복잡한 문제를 간단한 문제로 나누어 문제를 풀어가는 것이다. 제일 쉬운 것부터 생각해보자.N이 1일 때, 계단 수는 몇개일까? 제일 앞의 자릿수가 i인 경우에 대해 모든 계단수를 구해보자. i계단수DP[N][i]0-0111221331441551661771881991 DP[N][i]는 '길이가 N이고 앞자리가 i인 계단 수의 개수'를 저장하는 리스..