yukicoder No.1011 Infinite Stairs (★2.5)

問題：No.1011 Infinite Stairs - yukicoder

解答：#472406 (C++14) No.1011 Infinite Stairs - yukicoder

解法：dp[i][j]：i回目の移動でj段目にいる通り数とする。

dp[i][j]はd[i]の最大d個の累積和になるが、累積和はj-1の計算結果を使いまわしてO(1)で計算できる。

インデックスの処理として、当解法ではi回目の移動で到達できる最も低い段数をj=0とした。