[解答-伯俊]10844単純な階段数
解答方法
dpリスト(サイズ10)を準備します.現在の0から9の数字が含まれています(可能な場合).
現在のビット数がnである場合、数字はdp[n−1]+dp[n+1]である.
文字列の長さは最大100なので、10個の数字で合計100回計算されるので、100×10 x 2です.
時間の複雑さ
O(n x 10 x 2) = O(n)
コード#コード#
N = int(input())
dp = [1] * 10
dp[0] = 0
for i in range(1,N):
temp = [0] * 10
for j in range(10):
nj = j - 1
if 0 <= nj:
temp[j] += dp[nj]
nj = j + 1
if nj < 10:
temp[j] += dp[nj]
dp = temp[:]
print(sum(dp)%1000000000)Reference
この問題について([解答-伯俊]10844単純な階段数), 我々は、より多くの情報をここで見つけました https://velog.io/@psj8532/문제풀이-백준-10844.-쉬운-계단-수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol