不想写whk作业了来补一补之前没写出来的题。。。

当时做这题的时候一直在想有没有什么贪心方法，结果到最后没想出来，后来一看标签是动规，很快就写出来了。

状态转移方程很好想，

$f(i, j) \iff f_{i, j} \\f(i, j) =  \begin{cases} S(1, i) &\text{if} \ j = 0 \\ \displaystyle{\min_{j - 1}^{i - 1}(f(k, j - 1) + S(k+ 1, i))} &\text{otherwise} \end{cases}$

其中 $f(i, j)$ 表示在前 $i$ 个数字中共添加 $j$ 个加号时的最小值