このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。
問題
ポイント
動的計画法で解きます。
L 段目までは1歩ずつあがるしかないので1通り
L 段目以降は今の段目-L段目からL段飛び越してくる方法と、i-1段目から1つ上がる方法があります
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N, L = map(int, input().split(" "))
dp = [0 for _ in range(N+2)] # インデックスと段目をあわせるためにN+1項の数列
dp[0] = 1
for i in range(1, N+1):
if i + 1 < L:
dp[i] = dp[i - 1] % (10**9+7)
else:
dp[i] = (dp[i - 1] + dp[i - L]) % (10**9+7)
print(dp[N])
if __name__ == '__main__':
main()
