AtCoder Educational DP Contest / DP まとめコンテスト B - Frog 2

dp_b

動的計画法

前問のAの範囲が２つ前までだったのに対し、今回はKつ前までとなる。

問題自体は難しくないが、普通に解くと計算量がO(nk)となり、pythonでは間に合わない(numpy使って工夫しないかぎり)。

一応、pythonコード

c++コード