出たコンテストで初めて見るタイプのDPがあって頑張って理解したのでゆるく証明します。
簡単に言うと、以下の形のDPに対して $\mathrm{dp} (n, k)$ を $O(n k^{\frac{3}{4}})$ 時間で求められるという主張です。
$$ \mathrm{dp} (i+1, j) = \max_{1 \leq d \leq j} \left\{ \bigcirc \cdot \mathrm{dp} \left(i, \left\lceil \frac{j}{d} \right\rceil \right) \right\}. $$
ここで、 $\bigcirc$ は状態 $(i, \lceil j / d \rceil )$ から $(i+1, j)$ への遷移に対して最適な $d$ が $O(1)$ 時間で計算できるような値です（ $d$ について単調性があるなど）。
ゆるい証明
コールグラフ的なものを考えて説明します。 すなわち、状態 $(i, j)$ を頂点として、上記の式の$\mathrm{dp}(i, j)$ の計算で $\mathrm{dp} (i’, j’)$ の値を用いるとき $(i, j)$ から $(i’, j’)$ へ辺を貼ったグラフ $G$ を考えます。 グラフ $G$ において、 $(n, k)$ から到達可能な頂点集合、すなわち $\mathrm{dp} (n, k)$ の計算の際に用いられる引数の集合を $V_{n,k}$ とします。
天下り的ですが、実はこのとき以下の2つの主張が成り立ちます。
$\{j \mid (i, j) \in V_{n,k}\} = \{\lceil k / d \rceil \mid 1 \leq d \leq k \}$
重複する辺を除いたとき、$|E(G[V_{n,k}])| = O(n k^{\frac{3}{4}})$
1つ目は、 $\mathrm{dp}(n, k)$ を計算する際に状態 $(i, j) \in \{1, 2, \dots, n\} \times \{1, 2, \dots, k\}$ に対してテーブルを埋める必要はなく、 $j$ が $k$ の商であるもののみ埋めればよいことを意味します。 $k$ の商は$O(\sqrt{k})$個ですから、各 $i$ に対して $O(\sqrt{k})$ 個の状態しかありません。
また、下記の仮定より、$\mathrm{dp}(i + 1, j)$ は $\mathrm{dp}(i, \ast)$ の行を全てチェックすると $O(\sqrt{k})$ 時間で計算できますが、これだと計算量は $O(n \sqrt{k} \cdot \sqrt{k}) = O(nk)$ 時間となってしまいます。
$\bigcirc$ は状態 $\left(i, \lceil j / d \rceil \right)$ から $(i+1, j)$ への遷移に対して最適な $d$ が $O(1)$ 時間で計算できる
実は $\mathrm{dp}(i + 1, j)$ の計算をする際に、 $j’$ を $j$ の商として $\mathrm{dp}(i, j’)$ のみチェックするだけで、$O(n k^{\frac{3}{4}})$ 時間になるというのが、2つ目の主張です。
主張1の証明
任意の $\lceil k / d \rceil$ と $1 \leq d’ \leq \lceil k / d \rceil$ について以下が成り立つことを示せば十分です。 $$ \left\lceil \frac{\left\lceil \frac{k}{d} \right\rceil}{d’} \right\rceil = \left\lceil \frac{k}{d d’} \right\rceil. $$
$\lceil k / d \rceil = k / d$ のときは明らかですから、 $k = ad + b \ (b \in [1, d-1])$ とします。上述の式に代入すると、それぞれ $$ \left\lceil \frac{a+1}{d’} \right\rceil, \left\lceil \frac{a + \frac{b}{d}}{d’} \right\rceil $$ となります。 ここで、$0 < b/d < 1$ですから、 $$ \left\lceil \frac{a + \frac{b}{d}}{d’} \right\rceil = \left\lceil \frac{a + 1}{d’} \right\rceil $$ と評価できます。
主張2の証明？
$\mathrm{dp}(i + 1, j)$ の計算をする際に、 $j’$ を $j$ の商として $\mathrm{dp}(i, j’)$ のみチェックするだけで、$O(n k^{\frac{3}{4}})$ 時間になるというのが、2つ目の主張です。
計算量をちゃんとあいまいに評価します。
$\mathrm{dp}(i, \ast)$ から $\mathrm{dp}(i + 1, \ast)$ を計算する計算量が $O(k^{\frac{3}{4}})$ になっていることを確認すれば十分です。
上記の計算量は、こんな感じで評価できるらしいです。ただし、 $Q(x)$ で $x$ の商全体の集合を表します。 $$ \sum_{x \in Q(k)} |Q(x)| \simeq \sum_{\sqrt{k} \geq x \in Q(k)} \left( Q(x) + Q \left(\left\lceil \frac{k}{x} \right\rceil \right) \right) = \sum_{\sqrt{k} \geq x \in Q(k)} O\left(\sqrt{\frac{k}{x}}\right) = O(k^{\frac{3}{4}}). $$
積分すると、$O(k^{\frac{3}{4}})$になるそうです。
$$ \sum_{r\in R}\sqrt{r}\leq \sum_{i=1}^{\sqrt{k}}(\sqrt{i}+\sqrt{\frac{k}{i}}) \leq 2\sum_{i=1}^{\sqrt{k}}\sqrt{\frac{k}{i}} \leq 2\int_{0}^{\sqrt{k}} \sqrt{\frac{k}{x}}\text{d}x =4\sqrt{kx}\bigm|_0^{\sqrt{k}}=4k^{\frac{3}{4}} $$ 引用元: https://codeforces.com/blog/entry/113672?#comment-1011533
応用例
問題
Codeforces の Another n-dimensional chocolate bar という問題です。 本質部分だけ抜き出すと、次の問題です。
$n$ 個の正の整数からなる列 $a = (a_1, a_2, \dots, a_n)$ と正の整数 $k$ が与えられる。$n$ 個の正の整数からなる列 $b = (b_1, b_2, \dots, b_n)$ で $b_1 b_2 \dots b_n \geq k$ を満たすものに対する以下の式の最大値を求めたい。 $$ \left\lfloor \frac{a_1}{b_1} \right\rfloor \left\lfloor \frac{a_2}{b_2} \right\rfloor \dots \left\lfloor \frac{a_n}{b_n} \right\rfloor. $$
ただし、 $n \leq 100$, $k \leq 10^9$, $a_1 a_2 \dots a_n \geq k$ を満たす。
解法
$\mathrm{dp}(i, j)$ を、$i$ 番目まで見て $b_i$ の積が $j$ 以上のものの最大値とします。 すなわち、$i$ 個の正の整数からなる列 $b = (b_1, b_2, \dots, b_i)$ の列で $b_1 b_2 \dots b_i \geq j$ を満たすものに対する以下の式の最大値とします。 $$ \left\lfloor \frac{a_1}{b_1} \right\rfloor \left\lfloor \frac{a_2}{b_2} \right\rfloor \dots \left\lfloor \frac{a_i}{b_i} \right\rfloor. $$ 答えは明らかに $\mathrm{dp}(n, k)$ です。
さて、 $\mathrm{dp}(i + 1, j)$ の計算を考えます。
$b_{i+1} = d$ と固定した場合の最大値は、どのように計算できるでしょうか。 $b_1 b_2 \dots b_{i+1} \geq j$の条件を満たすためには、 $b_1 b_2 \dots b_i$ の整数性から $b_1 b_2 \dots b_i \geq \left\lceil j / b_{i+1} \right\rceil$ が必要十分となります。 一方で、 $\mathrm{dp}(i, j)$ は $j$ について単調減少ですから、最大値は以下の値となります。 $$ \left\lfloor \frac{a_{i+1}}{d} \right\rfloor \cdot \mathrm{dp} \left(i, \left\lceil \frac{j}{d} \right\rceil \right). $$
以上から、$\mathrm{dp}(i + 1, j)$ は以下のとおり計算できます。 $$ \mathrm{dp} (i+1, j) = \max_{1 \leq d \leq j} \left\{ \left\lfloor \frac{a_{i+1}}{d} \right\rfloor \cdot \mathrm{dp} \left(i, \left\lceil \frac{j}{d} \right\rceil \right) \right\}. $$
そして、$\lfloor a_{i+1} / d \rfloor$ が $d$ について単調非増加であることから、 $\lceil j / d \rceil$ が同じ値となる $d$ については最小のものだけ計算すれば十分です。 そして、そのような $d$ は商の列挙時に同時に求められます（参照: touristのコード）。 したがって、今回紹介した手法で $O(n k^{\frac{3}{4}})$ 時間で $\mathrm{dp}(n, k)$ が計算でき、TLに間に合います。