[動的計画法の最適化] Knuth optimization in DP

LeetCodeをやっていて学んだ。
個人wikiに書いていたが、せっかくなので誰かのためになると信じて共有する。

背景

Leetcode でこのゲーム理論の問題を解いている時に学んだ。詳細はこの記事では解説しないが、O(N^3) 時間かかるアルゴリズムを O(N^2) 時間に最適化するために必要だった。

1563. Stone Game V

実際にknuth optimizationを使用した自分の解答はこれ。

アルゴリズム

早速説明する。

Knuth optimization is what I can use in range DP.

@cache
def min_cost(start, end):
    for mid in range(start, end):
        # With knuth optimization, I can find the "best cut", which minimizes:
        # cost(mid) + min_cost(start, mid) + min_cost(mid + 1, end)

Note that cost() function must satisfy the following conditions.

For a ≤ b ≤ c ≤ d,

1. (MLI) It is a Monotone on the lattice of intervals: [cost(b, c) ≤ cost(a, d)]
2. (QI)  It satisfies the quadrangle inequality:       [cost(a, c) + cost(b, d) ≤ cost(b, c) + cost(a, d)]

That being said, Knuth optimization tells this. Use this to reduce the number of mids to be checked in L5.

best_cut[i][j-1] - 1 <= best_cut[i][j] <= best_cut[i+1][j] + 1

Now, use bottom up DP to make use of this optimization. Fill in cells in this order, so that I can reduce the candidates of the best cut in each (start, end).