백준 쉬운 계산수

분류 : 다이나믹 프로그래밍https://www.acmicpc.net/problem/10844풀이먼저 문제 이해를 하면 다음과 같다.계단 수는 인접한 모든 자리의 차이가 1인 수이다.N이 주어질 때, 깊이가 N인 계단 수의 갯수를 구하는 문제이다.0으로 시작하는 수는 계단 수가 아니다.결과는 10^9로 나눈 나머지를 출력해야한다.문제 풀이를 위해서 DP 알고리즘을 사용한다.dp[i][j]를 길이가 j이고 마지막 숫자가 i인 계단 수의 갯수라고 정의한다.점화식을 세우면 다음과 같다.dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1]즉, 길이가 i이고 끝자리가 j인 계단 수는 이전 자리(i-1)에서 끝자리가 j-1이거나 j+1이었던 경우의 합이다.초기 조건으로는dp[0][1] = 0 (0으..