Educational DP Contest N コード 問題 区間 \([i, j)\) のスライムが合体したときに支払うコストの最小値を \(C(i, j)\) とすると, \[C(i, j) = \min_{i \lt k \lt j} \left( C(i, k) + C(k, j) + \sum_{k=i}^{j-1} a_k \right)\] となる. これをメモ化再帰で計算する. 和の部分は累積和をあらかじめ計算しておく. 計算量は \(O(N^2)\) である.