公式解説と同じ動的計画法を行います。以下が遷移の式です。

\[ \mathrm{dp}[i][j] = \min_{0 \leq k \leq j} \left\lbrace \mathrm{dp}[i-1][j-k] + \left\lceil \frac{\max \left\lbrace D_i-kL_1, 0 \right\rbrace}{L_2} \right\rceil \right\rbrace \]

\(\min\) の添え字を遷移元を基準に書き換えて

\[ \mathrm{dp}[i][j] = \min_{0 \leq k \leq j} \left\lbrace \mathrm{dp}[i-1][k] + \left\lceil \frac{\max \left\lbrace D_i-(j-k)L_1, 0 \right\rbrace}{L_2} \right\rceil \right\rbrace \]

更に内側の \(\max\) を場合分けして外します

\[ \mathrm{dp}[i][j] = \min_{0 \leq k \leq j} \begin{cases} \mathrm{dp}[i-1][k] + \left\lceil \frac{D_i-(j-k)L_1}{L_2} \right\rceil \quad & \left( D_i-(j-k)L_1 \geq 0 \right) \\ \mathrm{dp}[i-1][k] \quad & \left( D_i - (j-k)L_1 \lt 0 \right) \end{cases} \]

場合分けのそれぞれに該当する \(k\) は区間になっているため、\(D_i - (j-k)L_1 \lt 0\) のケースは累積 \(\min\) で容易に計算できます。よって、以下の式を高速に計算することを考えましょう (\(s\) は \(D_i - (j-s)L_1 \geq 0\) を満たす最小の \(s\) です )。

\[ \min_{s \leq k \leq j} \left\lbrace \mathrm{dp}[i-1][k] + \left\lceil \frac{D_i-(j-k)L_1}{L_2} \right\rceil \right\rbrace \]

\(\mathrm{dp}\) が整数であるため、切り上げを外側に持ってくることができます。

\[ \left\lceil \min_{s \leq k \leq j} \left\lbrace \mathrm{dp}[i-1][k] + \frac{D_i-(j-k)L_1}{L_2} \right\rbrace \right\rceil \]

更に \(k\) に依存しない部分を括り出して

\[ \left\lceil \frac{D_i - jL_1}{L_2} + \min_{s \leq k \leq j} \left\lbrace \mathrm{dp}[i-1][k] + \frac{kL_1}{L_2} \right\rbrace \right\rceil \]

\(\min\) の中はスライド最小値で複数の \(j\) について同時に計算できます。全体で時間計算量は \(\Theta(N K_1)\) です。