yukicoder No.533 Mysterious Stairs (★2.5)

解法：dp[i][j] を今i段目にいて、直前でj段上ったときの通り数としてdpする。

dpの遷移は配るdpとして if(j != 1) dp[i+j][j] += dp[i][1] のようにする。

初期化も少し肝で、1回上ったところからスタートするとやりやすい。すなわちdp[1][1] = 1, dp[2][2] = 1, dp[3][3] = 1からスタート。

下記のブログでいろいろな解法が紹介されています。行列累乗は見えなかった… buyoh.hateblo.jp

mini notes