设 $g_{j,k}$ 表示当前这一行前 $j$ 个格子粉刷 $k$ 次得到的最大价值。

设 $f_{i,j}$ 表示前 $i$ 行粉刷 $j$ 次得到的最大收益。

$\begin{array}{} g_{j,k}=\max\limits_{p=1}^j\{f_{p-1,k-1}+\max(s_{j}-s_{p-1},j-p+1-s_{j}+s_{p-1})\} \\ f_{i,j}=\max\limits_{k=1}^{\min(j,m)}f_{i-1,j-k}+g_{m,k} \end{array}$

时间复杂度为 $O(nm^2)$。