dp_c 動的計画法 現時点をiとし、aについて考える。 現在のa[i]を最大にするには、 a[i]に１つ前のa以外(b、またはcのうち大きいほう)を合計すればいい。 b,cについても同様。 そして、最終的に最大なものを出力。

dp_b 動的計画法 前問のAの範囲が２つ前までだったのに対し、今回はKつ前までとなる。 問題自体は難しくないが、普通に解くと計算量がO(nk)となり、pythonでは間に合わない(numpy使って工夫しないかぎり)。 一応、pythonコード c++コード

dp_a 動的計画法 現在位置をiとすると、以下の①②のうち、小さいほうをdp[i]とする。 ①abs(h[i] - h[i - 1]) + dp[i - 1] ②abs(h[i] - h[i - 2]) + dp[i - 2] ※dp[1]の場合、2つ前はないので注意