050.md

050 - Stair Jump (★3)

解答

#include <iostream>
#include <vector>

int main()
{
	// N 段の階段, 一歩で 1 段か L 段上る
	int N, L;
	std::cin >> N >> L;

	// 0 段目から N 段目までのパターン数を記録していく配列
	std::vector<int> dp(N + 1);

	// 0 段目では 1 通り
	dp[0] = 1;

	// i 段目 (i が 1～(L-1)) のときは
	// (i-1) 段目までのパターン数
	for (int i = 1; i < L; ++i)
	{
		dp[i] = dp[i - 1];
	}

	// i 段目 (i が L～N) のときは
	// (i-1) 段目までのパターン数 + (i-L) 段目までのパターン数
	for (int i = L; i < (N + 1); ++i)
	{
		dp[i] = (dp[i - 1] + dp[i - L]) % 1'000'000'007;
	}

	// 例: N = 5, L = 3 のとき
	//                     ___
	//                 ___|[4]
	//             ___|[3]  +
	//         ___|[2]  +  [2]
	//     ___|[1]  +  [1]
	// ___|[0]     [0]
	// = 1 = 1 = 1 = 2 = 3 = 4
	// [0] [1] [2] [3] [4] [5]

	// 最終段までのパターン数を出力
	std::cout << dp.back() << '\n';
}