Educational DP Contest / DP まとめコンテスト N - Slimes

Educational DP Contest / DP まとめコンテスト N - Slimesを解きました。

問題

隣り合うスライムをくっつけていっていくとき、かかるコストの最小値。ただしxとyのスライムをくっつけるときx + yのコストがかかる。

解説

いわゆる区間DPと呼ばれるものである。区間[l,r)に関する値をメモしておき、より長い区間の値を計算する。

O(N^3)

提出

• for文

• メモ化再帰

参考

• jupi jupro Educational DP Contest / DP まとめコンテスト (EDPC) : N - Slimes 解説動画