[python] 백준 - 10844 (쉬운 계단 수)

실버1 문제이며, 제한 시간은 1초이다.

문제

해결 과정

경우의 수를 쭉 써보니 점화식이 바로 나왔다.

dp[i] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

여기서 j가 9일 때는 dp[i - 1][j - 1]만 해주고 j가 0일 때는 dp[i - 1][j + 1]만 해준다. 또한 0으로 시작하는 수는 계단수가 아니므로 결과를 출력할 때 sum(dp[n]) - dp[n][0]을 해준다.