[伯俊/Python 3]10844簡単な階段数

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

に答える

これは,長さN,隣接数の差がいずれも1である全数の個数を求める問題である.このとき90,09は階段数ではありません.
これはダイナミックプログラミングの問題です.2 D dptableで解決できます.dp[i]は、N長の段差数の個数である.このときdp[i][j]は以下のようになる.

dp[i][j] => i의 길이를 가지며 숫자 j로 끝나는 계단 수의 개수

端数が1差であることからステップ数と呼ぶことができるので、nの長さを有し、端数jのステップ数の数字は以下のように表すことができる.

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

ただし、端数が0または9の場合、互いに隣接していても段差数ではないので、この場合は単独で排除すべきである.最終的には、次のように表現できます.

if j==0:
	dp[n][j] = dp[n-1][j+1]
elif j==9:
	dp[n][j] = dp[n-1][j-1]
else:
	dp[n][j] = dp[n-1][j-1] + dp[n-1][j+1]

10,000,000,000に分割しないと、数値が大きすぎてメモリが過剰になる可能性があるので、毎回処理します.

コード#コード#

# Initial
N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N+1)]
answer = 0
mod = 1000000000

# Make DP table
for i in range(1, 10):
    dp[1][i] = 1
if N > 1: 
    for i in range(2, N+1):
        for j in range(0, 10):
            if j == 0:
                dp[i][j] = dp[i-1][j+1] % mod
            elif j == 9:
                dp[i][j] = dp[i-1][j-1] % mod
            else:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod
        

# Answer
for i in range(10):
    answer = (answer + dp[N][i]) % mod
print(answer)