AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の50問目である「Stair Jump（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【050 – Stair Jump（★3）】
考察
考えた内容の概要
この問題は、階段を上る方法の総数を求めるという問題です。E869120君は一歩で1段かL段上ることができ、彼が0段目からN段目に到達するまでの移動方法の総数を求めることが目的です。
この問題の解決策として、動的計画法（DP）という手法を使用します。
考えたことの内容
この問題の解決策として、N段目に到達するための方法は以下の2つから導かれます：
- N-1段目にいて、そこから1段上がる
- N-L段目にいて、そこからL段上がる
これは、N段目の状態（すなわち、移動方法の総数）を考えるには、N-1段目およびN-L段目までの状態（それぞれの移動方法の総数）を参照すれば良いということを意味します。
N段目を考えるためにN-1段目の情報が必要で、N-1段目を考えるにはN-2段目の情報を必要として・・・
詰まる所、0段目の状態から1段目,2段目・・・と順に通り数をカウントして、最終的にN段目の状態を求めればよいです。
実装した内容
このアプローチを実装するために、DPテーブルを作成します。このテーブルの各要素dp[i]は、i段目に到達するための移動方法の総数を表します。
典型解法：動的計画法
コード
# 入力の読み込み
N, L = map(int, input().split())
# NがLより小さい場合、移動方法は1通りしかないので、1を出力してプログラムを終了
if N < L:
print(1)
exit()
# DPテーブルの初期化
dp = [0 for i in range(N+1)]
# 0からL-1までの各段については、移動方法は1通りしかない
for i in range(L):
dp[i] = 1
# L段目については、0段目から一気にL段上る方法と、1段ずつ上る方法の2通りがある
dp[L] = 2
# L+1段目からN段目までの各段については、直前の段から1段上る方法と、L段前から一気にL段上る方法の和が移動方法の総数となる
for i in range(L+1, N+1):
dp[i] = dp[i-1] + dp[i-L]
# 答えが大きくなりすぎるのを防ぐため、各段ごとに10^9 + 7で割った余りを求める
dp[i] %= 10**9+7
# N段目に至る移動方法の総数を出力
print(dp[-1])まとめ
前の問題【048 – I will not drop out（★3）】
次の問題【051 – Typical Shop（★5）】
コメント