2020-07-23 2010JOI春合宿1-3 Stairs 解説 JOI 解説 問題リンク 解説 動的計画法を適切に高速化する問題です。 を、 番目の階段に来る方法の総数とします。 を求めるとき、どこの階段からここまで上ってこられるかを考える。これは、尺取り法や二分探索を使えば高速に求められます。 そのような段のうち最も低いものの index を とすると、 から までの総和が求められればよいです。 これは累積和を求めておくことで実現できます。 このように、累積和などでDPが高速化できることは多いので、高速化できる部分に気づく必要があることもあります。