DP的五類優(yōu)化(2) - 快速冪，四邊形不等式

在上一章中，我們介紹了基于單調(diào)隊列和二進制DP的優(yōu)化懈玻。
今天我們來看另外3類巧婶，斜率優(yōu)化，四邊形不等式酪刀，快速冪優(yōu)化粹舵。

斐波那契數(shù)列

一般大學(xué)的DP課，都會從這個有名的數(shù)列講起骂倘。通常會給你們演示的遞歸寫法，發(fā)現(xiàn)在算接近40的菲波那切項的時候就長時間返回不出值了巴席。這種做法被證明是指數(shù)級的復(fù)雜度历涝。隨后便開始講解遞歸過程中，比如F(K) 在很多遞歸樹的分支里都被展開進行了重復(fù)計算漾唉。如果我們可以保存一個已經(jīng)算好的結(jié)果荧库，之后相同K的計算其實是可以復(fù)用之前這個算好的結(jié)果的。這就是記憶化搜索赵刑，也稱自頂向下的DP分衫。這種做法可以把原來的指數(shù)級別的時間復(fù)雜度給優(yōu)化到線性的。

其實這個數(shù)列還可以更快般此，這里就要用到矩陣乘法的思想了蚪战。在講這個之前，我們先來介紹一下快速冪是什么铐懊？

我們來看一道LEETCODE的題目

https://leetcode.com/problems/powx-n/

我們在算X 的 N次方時邀桑，最基本的做法是X 乘以N次。其實我們也可以用二進制的思想來用LOG N 的時間把它算出來科乎。
比如我們算4次方壁畸，我們可以用X^2 的結(jié)果直接再平方。同理算8次方的話，我們可以先把x^2 給算好捏萍，接下來只要算x^2 的四次方了太抓。然后我們把x^4算好，只要算它的平方了令杈。
那么如果是奇數(shù)怎么辦腻异，我們可以把當(dāng)前的值預(yù)先乘進答案里來解決。比如三次方我們發(fā)現(xiàn)是奇數(shù)这揣，我們可以先把X 乘一次到答案悔常，然后再算X^2即可。
所以會有如下代碼

public double myPow(double x, int n) {
    if (x == 0) return 0;
    if (n == Integer.MIN_VALUE) return (1 / x) * myPow(1 / x, Integer.MAX_VALUE);
    if (n < 0) return myPow(1 / x, -n);
    double res = 1, p = x;
    while (n > 0) {
        if (n % 2 == 1) res *= p; // 是奇數(shù)给赞，把答案先乘進結(jié)果
        p = p * p; // 把x 的基礎(chǔ) 變成 x^2
        n >>= 1; // 之后只需要求原來的一半次冪
    }
    return res;
}

上述是快速冪的基本思想机打。這里假設(shè)小伙伴們已經(jīng)知道了矩陣乘法是如何做的。以及1個 M * N 的矩陣乘以一個 N * K的矩陣結(jié)果是 M * K的矩陣片迅。如果不知道的残邀，可以看我的這篇博客或上網(wǎng)查閱資料。
博客里也介紹了只有方陣才有矩陣的冪柑蛇。

那么矩陣乘法快速冪的DP優(yōu)化的核心思想如下：
一組DP狀態(tài)芥挣，其實等價于一個向量。而DP狀態(tài)的轉(zhuǎn)移方程耻台，可以是對一個向量做變形的矩陣空免。那么本質(zhì)上從1個向量到另一個狀態(tài)的向量，是可以通過一個矩陣來做到盆耽。矩陣具有結(jié)合律蹋砚，我們可以先對右半部分矩陣用快速冪得到一個終極的變形矩陣，再乘以向量摄杂，就可以把O(N)的計算優(yōu)化到 O (LOG (N))
第一次接觸這個思想的小伙伴一定會覺得非常陌生坝咐，不過我們就拿斐波那契數(shù)列來下手。
我們可以知道斐波那契的遞推公式為 dp[i] = dp[i-1] + dp[i - 2]; 那么每一個新的數(shù)的計算依賴于前2個析恢，所以我們結(jié)果可以構(gòu)建這么一個向量為【dp[n], dp[n-1]】
那么怎么轉(zhuǎn)移呢墨坚，其實就是找用什么樣的矩陣和這個向量做乘法后，可以讓N ++
dp[n + 1] = dp[n] * 1 + dp[n - 1] *1; dp[n] = dp[n] * 1 + dp[n - 1] * 0;
我們可以發(fā)現(xiàn)映挂，只需要用【[1,1],[1,0]】這個矩陣對向量【dp[n], dp[n-1]】做乘法即可得到【dp[n+1], dp[n]】泽篮。

image.png

那么有了上述公式，如果要從 dp[1], dp[2] 求到 dp[n], dp[n-1] 中間需要有N-2個同樣的變形矩陣的乘法袖肥。

image.png

綜上我們可以實現(xiàn)如下代碼
https://leetcode.com/problems/fibonacci-number

public int fib(int N) {
    if (N == 0) return 0;
    if (N <= 2) return 1;
    int[][] dp = {{1, 1}}; // dp[2], dp[1]
    int[][] ma = {{1,1},{1,0}};
    N -= 2;
    while (N > 1) {
        if ((N & 1) == 1) dp = mul(dp, ma);
        ma = mul(ma, ma);
        N >>= 1;
    }
    dp = mul(init, ma);
    return dp[0][0]; // dp[n]
}
int[][] mul(int[][] a, int[][] b) { // 矩陣乘法 (m * n)  X (n * k) = m * k 
    int m = a.length, n = a[0].length, k = b[0].length;
    int[][] c = new int[m][k];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) {
            for (int p = 0; p < n; p++) {
                c[i][j] += a[i][p] * b[p][j];
            }
        }
    }
    return c;
}

另一道LEETCODE

https://leetcode.com/problems/knight-dialer/
這道題主要是講馬子跳躍法咪辱，然后再一個鍵盤上可能打出多少不同的數(shù)字，在跳N步之后椎组。比如跳1步油狂，那么就是10. 因為第一個鍵可以按在任何一個位置。跳2步，是20.
這道題可以直接TOP DOWN去做专筷，比如我的目標(biāo)是最后在1這個位置弱贼，跳完K步。那么能跳到1 的磷蛹，只有

image.png

我們這里定K=2,也就是求跳完2步的數(shù)量
所以就有 dfs(1, K=2） = dfs (6, K=1) +dfs(8, K=1)
K = 1 是遞歸出口吮旅，返回1就好了。
有了這個思路味咳，我們其實只要把每個點可以由哪些點跳過來的信息保存好庇勃。
就可以搜索了。

NEIGHBORS_MAP = {
  0: (4, 6),
  1: (6, 8),
  2: (7, 9),
  3: (4, 8),
  4: (3, 9, 0),
  5: tuple(), # 5 has no neighbors
  6: (1, 7, 0),
  7: (2, 6),
  8: (1, 3),
  9: (2, 4),
}

因為到達一個點之后K步槽驶，和之前怎么跳過來的是不相關(guān)的责嚷。所以我們可以人為無論前面怎么跳，你現(xiàn)在跳到了M的數(shù)字掂铐，并且還有K步罕拂，余下到1的可能性都是不變的。那么就可以引入記憶化搜索來避免重復(fù)的遞歸展開計算全陨。這樣時間復(fù)雜度就是狀態(tài)數(shù)量 * 每次遞歸函數(shù)要做的操作爆班。狀態(tài)數(shù)量是 10 * K（K為跳的步數(shù)）
其實這道題就解決了。
其實我們可以發(fā)現(xiàn)這道題也是當(dāng)前的狀態(tài)是通過上一步的狀態(tài)辱姨，根據(jù)固定的公式去轉(zhuǎn)移的柿菩，最后是去求個數(shù)，我們就可以使用矩陣來為向量做變換的思想把它優(yōu)化到LOG (N)炮叶。
上面這個鄰居信息表的含義其實就是dp[i][1] = dp[i-1][4] + dp[i-1][6];
那么我們把需要的位置給設(shè)置成系數(shù)1碗旅，不需要的位置設(shè)置成系數(shù)0，上面的MAP等價于下面的矩陣

NEIGHBORS_MAP = {
  0: (0, 0, 0, 0, 1, 0, 1, 0, 0, 0),
  1: (0, 0, 0, 0, 0, 0, 1, 0, 1, 0),
  2: (0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
  3: (0, 0, 0, 1, 0, 0, 0, 0, 1, 0),
  4: (1, 0, 0, 1, 0, 0, 0, 0, 0, 1),
  5: (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
  6: (1, 1, 0, 0, 0, 0, 0, 1, 0, 0),
  7: (0, 0, 1, 0, 0, 0, 1, 0, 0, 0),
  8: (0, 1, 0, 1, 0, 0, 0, 0, 0 ,0),
  9: (0, 0, 1, 0, 1, 0, 0, 0, 0, 0),
}

接下來的事情似乎就是用快速冪镜悉，來求終極變換方案。然后把初始向量和終極矩陣方案直接相乘医瘫。然后把1~10的值求和即可侣肄。
如果理解的斐波那契那里的代碼，下面其實是一樣一樣的醇份。
注意因為向量是行向量稼锅，所以做乘法的時候，是和矩陣的列去乘僚纷，所以上面的MAP矩距，再轉(zhuǎn)矩陣的時候，應(yīng)該從行映射到矩陣的列怖竭。比如上面的MAP的第一行其實等價下面矩陣的第一列锥债。當(dāng)然你定義初始向量為列向量，就可以不用做這個變換。

int M = 1000000007;
public int knightDialer(int n) {
    long[][] m = {{0,0,0,0,1,0,1,0,0,0},
                  {0,0,0,0,0,0,1,0,1,0},
                  {0,0,0,0,0,0,0,1,0,1},
                  {0,0,0,0,1,0,0,0,1,0},
                  {1,0,0,1,0,0,0,0,0,1},
                  {0,0,0,0,0,0,0,0,0,0},
                  {1,1,0,0,0,0,0,1,0,0},
                  {0,0,1,0,0,0,1,0,0,0},
                  {0,1,0,1,0,0,0,0,0,0},
                  {0,0,1,0,1,0,0,0,0,0}};
    long[][] res = {{1,1,1,1,1,1,1,1,1,1}};
    n--;
    while (n > 0) {
        if (n % 2 == 1) res = mul(res, m);
        m = mul(m , m);
        n /= 2;
    }
    long sum = 0;
    for (long i : res[0]) {
        sum += i;
    }
    return (int) (sum % M);
}
// A[m][p] * B[p][n] = C[m][n]
long[][] mul(long[][] a, long[][] b) {
    int m = a.length, n = b[0].length, p = a[0].length;
    long[][] res = new long[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < p; k++) {
                res[i][j] += a[i][k] * b[k][j];
                res[i][j] %= M;
            }
        }
    }
    return res;
}

什么樣的問題可以用矩陣快速冪優(yōu)化

我們看到這里發(fā)現(xiàn)這里有個狀態(tài)機轉(zhuǎn)化的思想哮肚，我們把它寫成矩陣和向量的乘法形式登夫，這類DP都可以使用快速冪; 當(dāng)然這種題目會要求去求個數(shù)，而不是MIN/ MAX
但并不是只要是狀態(tài)機變化的計數(shù)DP都可以用矩陣乘法快速冪允趟。比如經(jīng)典的DECODE ways恼策，https://leetcode.com/problems/decode-ways/

雖然他是從DP[N-1] 和 DP[N-2] 過來，但是里面涉及到了條件分支潮剪，這種題目無法寫成矩陣變換的形式涣楷。

下面我們再看一道可以用快速冪的思想去解的題，然后看我們怎么定義不同的狀態(tài)使得可以用不同的矩陣轉(zhuǎn)換來表示的情況抗碰。

https://leetcode.com/problems/student-attendance-record-ii/

題目中要求一個學(xué)生最多只能出現(xiàn)1個A狮斗，和2個連續(xù)的L（也就是說不要求L的總數(shù)，只要沒有3個連續(xù)的L即可）

同時我們發(fā)現(xiàn)這道題也是求個數(shù)改含，我們可以之后思考是否可以用快速冪來優(yōu)化情龄。

我們看怎么來定義DP的狀態(tài)。首先A和L一定會在狀態(tài)機里的捍壤。不可以定dp[n][i][j] 表示第N天時骤视，這個學(xué)生已經(jīng)連續(xù)i天是L了，且歷史上發(fā)生了j次A

那么根據(jù)這個狀態(tài)鹃觉，我們可以知道如果i >0 那么其實只能從dp[n-1][i-1][j]轉(zhuǎn)移過來专酗，因為你希望連續(xù)2天是L，必然要從連續(xù)1天是L轉(zhuǎn)過來盗扇。

如果i = 0的時候祷肯，可以從其他所有狀態(tài)轉(zhuǎn)過來，因為只要再結(jié)尾加個P或加個A疗隶，就可以破壞掉連續(xù)i天是L的連續(xù)佑笋。根據(jù)這個思路，我們也可以列出關(guān)系MAP斑鼻。

NEIGHBORS_MAP = {
  k,0,0: (k-1, 1, 0),  (k-1, 2, 0),  (k-1, 0, 0) [最后加P]
  k,1,0: (k-1, 0, 0)[最后加L]
  k,2,0: (k-1, 1, 0)[最后加L]
  k,0,1: (k-1, 1, 0),  (k-1, 2, 0),  (k-1, 0, 0) [最后加A]  (k-1, 1, 1),  (k-1, 2, 1),  (k-1, 0, 1) [最后加P]
  k,1,1: (k-1, 0, 1)[最后加L]
  k,2,1: (k-1, 1, 1)[最后加L]
}

有了上述的MAP蒋纬，我們就可以很方便的轉(zhuǎn)換成矩陣。這里我們要對I,J 做編碼坚弱。因為J最多2種取值蜀备。所以編碼之后的數(shù)為 i * 2 + j
那么矩陣就是

0: 1,1,1,0,0,0
1: 1,0,0,0,0,0
2: 0,1,0,0,0,0
3: 1,1,1,1,1,1
4: 0,0,0,1,0,0
5: 0,0,0,0,1,0

有了這些,下面我們來思考初始向量是什么，根據(jù)定義荒叶，在最開始只有可能是沒有A,沒有L碾阁，所以只有dp[0][0][0] = 1,其他都為0.
最后記得把這6種狀態(tài)結(jié)尾的個數(shù)做一個求和即是題目的答案

int M = 1000000007;
public int checkRecord(int n) {
    long[][] m = new long[][]{
        {1,1,0,1,0,0},
        {1,0,1,1,0,0},
        {1,0,0,1,0,0},
        {0,0,0,1,1,0},
        {0,0,0,1,0,1},
        {0,0,0,1,0,0}
    };
    long[][] res = new long[][]{{1,0,0,0,0,0}};
    while (n > 1) {
        if (n % 2 == 1) res = mul(res, m);
        m = mul(m, m);
        n >>= 1;
    }
    res = mul(res, m);
    long sum = 0;
    for (int i = 0; i < 6; i++) sum += res[0][i];
    return (int) (sum % M);
}

我們再來看一個狀態(tài)的表示方法，之前我們定義的是結(jié)尾有多少個L些楣。這里我們可以定義結(jié)尾最多可能有多少個L脂凶。這樣定義的好處是最后不用作那個求和宪睹。因為我們的狀態(tài)是最多有多2個L，所以也包含了1個L和0個L的情況了艰猬。為了把A也給不求和横堡，所以我們把狀態(tài)也轉(zhuǎn)成歷史上最多有了多少個A
這樣我們最后只要返回dp[n][2][1] 就是所有結(jié)果。
那么因為都改為最多冠桃，所以第一個變化的就是初始向量命贴，原來除了0,0 其他都不合法。現(xiàn)在因為是最多食听，也就是L和A可有可無胸蛛。所以求變得全合法了。

long[][] res = new long[][]{{1,1,1,1,1,1}};

然后狀態(tài)轉(zhuǎn)移是如何呢樱报，我們知道0,0 現(xiàn)在只能從前一個2,0過來了葬项，不然就破壞了最多的定義。因為只要加一個P迹蛤，就可以使得結(jié)尾最多又恢復(fù)到0個L民珍。
1,0 也可以從2,0轉(zhuǎn)過來（通過最后加P）
也可以從（0,0）轉(zhuǎn)過來，通過最后加L盗飒。但是不能最后加A嚷量，因為當(dāng)前定義是歷史上最多0個A。（注意歷史上最多和只看結(jié)尾上最多還是有區(qū)別的）

所以我們發(fā)現(xiàn)任何狀態(tài)都可以從（0,2）轉(zhuǎn)過來逆趣，因為最后都可以加P蝶溶。

只有當(dāng)I >0時，可以從（i-1宣渗， x)轉(zhuǎn)過來抖所，通過加L, 注意這里的X和上一個狀態(tài)要一致，因為這里是歷史上最多痕囱。

當(dāng)J >0田轧，可以從（2， j -1)轉(zhuǎn)過來, 通過加A鞍恢。這里前面可以直接取最大值2涯鲁，因為加了一個A我們就不會讓最多2個L的性質(zhì)不合法，所以可以取2.

那么下面就是寫轉(zhuǎn)移矩陣了有序。因為所有通過加P 都可以從(2,0)轉(zhuǎn)移過來慨蛙，我們可以看到第二列全是1

0: 0,0,1,0,0,0
1: 1,0,1,0,0,0
2: 0,1,1,0,0,0
3: 0,0,1,0,0,1
4: 0,0,1,1,0,1
5: 0,0,1,0,1,1

下面只要改一下初始矩陣赁咙，和變換矩陣拢军，其余代碼不用動尉剩，最后直接返回即可码秉。

int M = 1000000007;
public int checkRecord(int n) {
    long[][] m = new long[][]{
        {0,1,0,0,0,0},
        {0,0,1,0,0,0},
        {1,1,1,1,1,1},
        {0,0,0,0,1,0},
        {0,0,0,0,0,1},
        {0,0,0,1,1,1}
    };
    long[][] res = new long[][]{{1,1,1,1,1,1}};
    while (n > 1) {
        if (n % 2 == 1) res = mul(res, m);
        m = mul(m, m);
        n >>= 1;
    }
    res = mul(res, m);
    return (int) res[0][5];
}

講了這么多菌瘫，我們最后再來總結(jié)一下快速冪優(yōu)化的思想奈偏，就是把計數(shù)的狀態(tài)機轉(zhuǎn)換的DP飞几，通過把初始狀態(tài)表示為初始向量，轉(zhuǎn)移方程表示為變換矩陣缩膝。通過矩陣快速冪的方式優(yōu)化時間復(fù)雜度從O(n) 到 O(log(n))的一類技巧混狠。

講到這里矩陣快速冪優(yōu)化就要告一段落，再開始新的篇章前疾层，我給你們留一道思考題将饺。

上題中L和A 都是定值，如果L和A痛黎，是可變的（假設(shè)2者之和不超過10）,你該如何實現(xiàn)LOG N的算法呢予弧？

四邊形不等式優(yōu)化

四邊形不等式DP理論非常復(fù)雜，編碼還是比較簡單湖饱。
先說下他的由來掖蛤。我們都知道一個東西叫最優(yōu)樹。還記得我們在學(xué)編碼時的哈夫曼數(shù)嗎井厌，因為每個字母的出現(xiàn)頻率不一樣蚓庭，所以我們希望頻率高的編碼盡可能短，就有了哈夫曼樹的思想仅仆。他就是貪心的去合并權(quán)值最小的2個樹器赞，最后合到一顆為止。該樹即為所求的哈夫曼樹蝇恶。
隨后計算機鼻祖高納德在解決最優(yōu)二叉搜索樹時發(fā)明的一個算法拳魁，隨后姚期智的夫人，做了深入研究撮弧，擴展為一般性的DP優(yōu)化方法潘懊。可以把一些時間復(fù)雜度O(n^{3)的DP問題優(yōu)化到O(n}2), 所以這個方法又被成為 (Knuth-Yao speedup theorem)

最優(yōu)二叉搜索樹問題：

現(xiàn)有 n 個排序過的數(shù)贿衍，記為數(shù)組 a授舟。為敘述方便使 a 的下標(biāo)從 1 開始。已知給定兩組概率 P1...PN 和 Q0...QN贸辈，Pi 為“每一次搜索的目標(biāo)正好為 a i的概率释树， Qi
為“每一次搜索的目標(biāo)正好在a (i) 和 a (i+1) 之間”的概率，其中設(shè)邊界值 a (0)
為負(fù)無窮擎淤，邊界值 a (n+1)為正無窮奢啥。求根據(jù)這些概率組成一個高效的二叉搜索樹，使得每次搜索的平均時間最小化嘴拢。只需要返回該樹的最優(yōu)平均時間桩盲，不需要表達或者返回樹的結(jié)構(gòu)。

我們來思考下因為二叉搜索樹需要保持節(jié)點本身有序的特性席吴，所以我們不能像哈夫曼樹那樣貪心的取2個概率最小的子樹去合并赌结，因為會破壞搜索樹的特性捞蛋。其實這里等價于只有相鄰的子樹可以合并。這樣我們可以把最小的子問題給求好柬姚，然后依據(jù)最小求次小拟杉。次小的時候我們需要枚舉決策點，然后再所有決策點里找最小量承。這樣的做法是O(n^3)的搬设。
因為要遍歷N層，每一層我們要遍歷N個窗口宴合，每個窗口我們又要枚舉最優(yōu)決策點焕梅。
我們來看下N^3的代碼如實寫

double calculateOptimalBST(double[] recordProbability, double[] gapProbability) {
    int n = gapProbability.length;
    double[][] dp = new double[n+1][n+1];
    double[][] subTreeProbabilitySum = new double[n+1][n+1];
    for (int i = 1;i <= n; i++) {
        dp[i][i - 1] = gapProbability[i-1];
        subTreeProbabilitySum[i][i - 1] = gapProbability[i-1];
    }
    for (int len = 1; len < n; len++) { // 枚舉節(jié)點數(shù)為LEN的子樹的最優(yōu)解
        for (int i = 1; i < n + 1 - len; i++) { // 滑動每一個窗口i~j
            int j = i + len - 1;
            subTreeProbabilitySum[i][j] =
                    subTreeProbabilitySum[i][j - 1] + recordProbability[j] + gapProbability[j];
            dp[i][j] = Double.MAX_VALUE;
            for (int k = i; k <= j; k++) { // 枚舉決策點,K是根節(jié)點
                if (dp[i][j] > dp[i][k-1] + dp[k+1][j]) {
                    dp[i][j] = dp[i][k-1] + dp[k+1][j]; // 左右子樹的搜索代價各加一層
                }
            }
            dp[i][j] += subTreeProbabilitySum[i][j]; // 有這個樹的搜索代價加一層
        }
    }
    return dp[1][n - 1];
}

上面的代碼我們可以跑2個簡單的例子論證下正確性
比如，只含一個節(jié)點的樹卦洽，他的最優(yōu)解就是本身贞言，但是左右的GAP 因為在遍歷的時候是需要搜到NULL節(jié)點才能確定這個值不存在，所以搜的層數(shù)都為2.

Assert.assertTrue(0.2 + (0.3 + 0.5) * 2 ==
        calculateOptimalBST(new double[]{-1, 0.2}, new double[]{0.3, 0.5}));

我們再來驗證2個節(jié)點的情況阀蒂，加入第一個GAP區(qū)間概率很高该窗，我們應(yīng)該拿左邊的節(jié)點為根節(jié)點更優(yōu)。

Assert.assertTrue(0.25 + (0.4 + 0.15) * 2 + (0.08 + 0.12) * 3
        == calculateOptimalBST(new double[]{-1, 0.25, 0.15}, new double[]{0.4, 0.08, 0.12}));

我們再來驗證2個節(jié)點的情況蚤霞，加入最后一個GAP區(qū)間概率很高酗失，我們應(yīng)該拿右邊的節(jié)點為根節(jié)點更優(yōu)。

Assert.assertTrue(0.15 + (0.4 + 0.25) * 2 + (0.08 + 0.12) * 3
        == calculateOptimalBST(new double[]{-1, 0.25, 0.15}, new double[]{0.12, 0.08, 0.4}));

下面我們來講四邊形不等式優(yōu)化昧绣。
這個優(yōu)化的證明過程非常繁瑣规肴，我這里只講技巧，具體證明我給大家一些不錯的資料夜畴，有興趣的朋友大家可以根據(jù)資料去學(xué)習(xí)拖刃。比如B站的這個視頻

這類的優(yōu)化過程通常是這樣的，比如原來的O（N^3）的寫法是這樣

image.png

優(yōu)化之后的代碼會長這樣

image.png

上面我們引入一個關(guān)鍵的S表贪绘，他代表我們之前求過的最優(yōu)決策兑牡。
這個決策表會有一些初始值我們需要賦值，之后就是用最優(yōu)決策來鎖定第三層循環(huán)的范圍税灌。被證明可以讓第三層在第二層下的總次數(shù)是O （N）的均函。也就是表面上看是2層循環(huán)，但是實際只有O（N）的遍歷次數(shù)菱涤，具體可以通過打CNT苞也，每遍歷一次
CNT++來直觀感受。

下面我們來分析什么時候可以用四邊形不等式粘秆。

1墩朦、如果上述的w函數(shù)同時滿足區(qū)間包含單調(diào)性和四邊形不等式性質(zhì)，那么函數(shù)dp也滿足四邊形不等式性質(zhì)
我們再定義s(i,j)表示 dp(i,j) 取得最優(yōu)值時對應(yīng)的下標(biāo)（即 i≤k≤j 時翻擒，k 處的 dp 值最大氓涣，則 s(i,j)=k此時有如下定理

2、假如dp(i,j)滿足四邊形不等式陋气，那么s(i,j)單調(diào)劳吠，即 s(i,j)≤s(i,j+1)≤s(i+1,j+1)

所以也就是說只要W函數(shù)，有2個性質(zhì)巩趁，我們可以知道S[I,J]單調(diào)痒玩，那么就可以套模板來優(yōu)化。也就是第三層循環(huán)由原來的I~J议慰，變成S[I][J-1] ~S[I+1][J]

我們來看下什么是包含單調(diào)性和四邊形不等式性蠢古。

區(qū)間包含單調(diào)性：如果對于任意 a<=b<=c<=d ，均有w(b,c) <= w(a,d) 成立别凹，則稱函數(shù) w 對于區(qū)間包含關(guān)系具有單調(diào)性草讶。
四邊形不等式：如果對于任意 a <= b <= c <= d ，均有 w(a,c) + w(b,d) <= w(a,d) + w(b,c) 成立炉菲，則稱函數(shù) 滿足四邊形不等式（簡記為“交叉小于包含”）堕战。若等號永遠成立，則稱函數(shù) w 滿足四邊形恒等式拍霜。

我們回過頭來看上面最優(yōu)二叉搜索樹的W函數(shù)嘱丢。
本質(zhì)上是subTreeProbabilitySum，因為加的都是>=0很容易得出大區(qū)間一定>=小區(qū)間祠饺，所以滿足區(qū)間包含單調(diào)性
第二個四邊形不等式越驻，有時可以直接證明出來是滿足的，有些時候不太好想道偷，我們可以直接對W函數(shù)打表缀旁，然后驗證所有的ABCD，如果是滿足的试疙。那么大概率可以用四邊形不等式優(yōu)化诵棵。
我們來寫個打表函數(shù)。

for (int i = 1; i < n; i++) {
    for (int j = i; j < n; j++) {
        for (int k = j; k < n; k++) {
            for (int m = k; m < n; m++) {
                double contain = subTreeProbabilitySum[i][m] + subTreeProbabilitySum[j][k];
                double cross = subTreeProbabilitySum[i][k] + subTreeProbabilitySum[j][m];
                assert contain >= cross;
            }
        }
    }
}

如果沒有報錯祝旷，我們可以嘗試用一下四邊形不等式優(yōu)化履澳。

double calculateOptimalBST(double[] recordProbability, double[] gapProbability) {
    int n = gapProbability.length;
    double[][] dp = new double[n+1][n+1];

    double[][] subTreeProbabilitySum = new double[n+1][n+1];
    for (int i = 1;i <= n; i++) {
        dp[i][i - 1] = gapProbability[i-1];
        subTreeProbabilitySum[i][i - 1] = gapProbability[i-1];
    }
    int[][] s = new int[n+1][n+1]; // step 1. 引入決策表
    for (int i = 1; i <= n; i++) // step 4. 給s 賦初始值
        s[i][i - 1] = i;
    for (int len = 1; len < n; len++) {
        for (int i = 1; i < n + 1 - len; i++) {
            int j = i + len - 1;
            subTreeProbabilitySum[i][j] =
                    subTreeProbabilitySum[i][j - 1] + recordProbability[j] + gapProbability[j];
            dp[i][j] = Double.MAX_VALUE;
            int st = s[i][j-1], ed = Math.min(j, s[i+1][j]); // step 3. 用決策表更新搜索范圍
            for (int k = st; k <= ed; k++) {
                if (dp[i][j] > dp[i][k-1] + dp[k+1][j]) {
                    dp[i][j] = dp[i][k-1] + dp[k+1][j];
                    s[i][j] = k; // step2. 記錄最優(yōu)決策
                }
            }
            dp[i][j] += subTreeProbabilitySum[i][j];
        }
    }
    return dp[1][n - 1];
}

大致分為4步。

第一步怀跛，引入決策表距贷。
第二步，在更新時更新決策表吻谋。
第三步忠蝗，在第三層循環(huán)時，用決策表的數(shù)據(jù)來循環(huán)漓拾。
第四步阁最，是需要思考的戒祠，如何賦初始值。這道題因為最開始算的是DP[I][I]速种，也就是1的單位姜盈，那么對S[I][j]來說，他的前驅(qū)和后繼s[i][j-1] 和 s[i+1][j] 都是0 的單位配阵，所以要在賦初始值時用s[i][i-1]馏颂，其次就是在第一次循環(huán)時ed 這個位置因為只有一個長度好遍歷，所以這里要加個MIN

我們再來研究下這個優(yōu)化到底在遍歷什么棋傍？

首先我們會發(fā)現(xiàn)救拉，他是根據(jù)長度從小到大在遍歷每個窗口。在每層長度中瘫拣，每個窗口要遍歷的范圍則是S[i][j-1] 到 S[i+1][j]. 具體一下再LEN=1, I = 1時亿絮，其實就是 s[2][1] - s[1][0] 個決策點. 隨后I到2了，變成s[3][2] - s[2][1] 個決策點拂铡。那么發(fā)現(xiàn)前項和后項有正負(fù)號可以抵消壹无。所以最終一個LEN的遍歷次數(shù)就是 s[n-1][n-len+1] - s[len-1][0]。根據(jù)S數(shù)組的定義感帅，就是決策點斗锭，所有決策定都不會超過N，所以對于一個LEN來說失球，內(nèi)部2個循環(huán)和為s[n-1][n-len+1] - s[len-1][0] <= n.
就證明是O(n ^ 2) 了

我們可以看一道類似的題目
https://www.lintcode.com/problem/stone-game
這道題其實和最優(yōu)二叉樹還是比較像的岖是，區(qū)別就是不用考慮GAP區(qū)間。其實也就更加簡單实苞。
因為不考慮GAP區(qū)間豺撑，我們甚至可以直接證明COST[I,J] 是滿足四邊形恒等式的。
cost[a,d] = cost[a,b] + cost[b,c] + cost[c,d]

cost[a,c] = cost[a,b] + cost[b,c]
cost[b,d] = cost[b,c] + cost[c,d]
這樣變形之后帶入原式黔牵，就會發(fā)現(xiàn)左右兩邊相等聪轿。
另外一個最優(yōu)二叉搜索樹的DP[I,J] 其實是包含了gap[i-1] ~gap[j] 的。
所以枚舉最優(yōu)決策不讓左右最優(yōu)子樹的GAP有重疊需要從dp[i][k-1] 和 dp[k+1][j]來轉(zhuǎn)移猾浦。因為他們代表了gap[i-1]~gap[k-1] 和 gap[k]~gap[j]的2顆最優(yōu)子樹陆错。剛好排除了決策節(jié)點的全覆蓋。
而這道題因為不存在GAP金赦，DP[I,J]的定義也發(fā)生了變化音瓷，指的是合并stone[i] ~ stone[j], 所以枚舉K的時候，是dp[i][k] 和 dp[k+1][j]轉(zhuǎn)移過來夹抗，意思是最后是由[i,k]這堆石頭和[k+1, j]這堆石頭合并绳慎。
我們來看下直接用四邊形，因為石子這個問題，循環(huán)是從長度為2的情況開始（1是終態(tài)不用算的）杏愤，所以在初始化的時候是初始化1靡砌，而不是像上一題初始化0.這些都是要注意的細節(jié)。下面上代碼

public int stoneGame(int[] A) {
    int l = A.length;
    if (l == 0) return 0;
    int[][] dp = new int[l][l];
    int[][] s = new int[l][l];
    int[] presum = new int[l + 1];
    for (int i = 0; i < l; i++) {
        presum[i + 1] = presum[i] + A[i];
        s[i][i] = i;
    }
    for (int len = 2; len <= l; len++) {
        for (int i = 0; i < l - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE / 2;
            int st = s[i][j-1], ed = Math.min(j - 1, s[i+1][j]);
            for (int k = st; k <= ed; k++) {
                if (dp[i][k] + dp[k + 1][j] < dp[i][j]) {
                    dp[i][j] = dp[i][k] + dp[k + 1][j];
                    s[i][j] = k;
                }
            }
            dp[i][j] += presum[j + 1] - presum[i];
        }
    }
    return dp[0][l - 1];
}

通過四邊形不等式我們又把一道N^3的區(qū)間DP問題給優(yōu)化到了N ^ 2
這道題還有一種n log n的解法声邦，叫GarsiaWachs算法的最優(yōu)解法, 學(xué)有余力的小伙伴可以自行搜索學(xué)習(xí)

我們再來看一道這周周賽的一個問題

https://leetcode.com/problems/allocate-mailboxes/
這道題暴力的思路是乏奥，我們只分析前K個房子，假設(shè)此時要建M個郵局亥曹。我們已經(jīng)知道M-1個郵局，前0~K-1個房子下的最優(yōu)解恨诱。我們只要枚舉最后一個郵局建造的位置管轄的屋子媳瞪，然后不管轄的屋子靠前面算過的最優(yōu)子問題直接獲得答案即可得到當(dāng)前問題的答案。
因為這里最優(yōu)子問題是由2個維度組成N和K照宝。那么枚舉決策的時候還是要根據(jù)N來枚舉最后一步能管的房子數(shù)量蛇受。所以這道題DP 是O(N^3）的
DP方程為
dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k+1][i]);
其中dp[i][j]表示前i個村莊建j個郵局的最小距離和，k枚舉1到i的所有村莊厕鹃；w[k+1][i]表示第k+1個村莊到第i個村莊建一個郵局的最小距離和兢仰，有一個顯然的性質(zhì)：在某一段區(qū)間上建一個郵局，最小距離和為在其中點村莊上建

那么我先來思考怎么快速的把這個W數(shù)組給求出來
我們知道如果只有一個房子w[i][i] = 0.
如果有2個房子剂碴，我們是取中點建是最優(yōu)的把将。所以我們新加了一個房子就是加上他到中點的距離。

int mid=(i+j)/2;
w[i][j] = w[i][j-1]+abs(x[j]-x[mid]);

有讀者可能會問忆矛，除了最后一個點不算察蹲，為什么w[i][j] = w[i][j-1]，中點不是會隨著加了一個屋子催训，而往后移嗎洽议？
這個我們可以分類討論看，如果是從奇數(shù)房子增加到偶數(shù)房子漫拭。中點是不會移動的亚兄，所以可以等價。
如果是偶數(shù)房子增加到奇數(shù)房子采驻，中點是需要往后移動一格审胚。但是原來小于等于中點的房子數(shù)量是偶數(shù)的一半，我把中點往后移挑宠，這一半的房子的距離都要加上中點移動的距離菲盾。同時剩下一半的房子的距離都會減去中點移動的距離。因為2半的房子數(shù)量相同各淀，所以值還是不變的懒鉴。綜上這個等式是成立的。
那么我們就可以在O(N ^ 2）的時間求完W數(shù)組

接下來主要的時間瓶頸就是DP這個O(n * n * K)的復(fù)雜度。
這個式子dp[i][j] = min{ dp[i-1][k] + w(k+1,j) | i-1 <= k < j }乍一看和我們之前說到可以用四邊形不等式的式子dp[i][j] = min{ dp[i][k] + dp[k+1][j] + w(i,j) | i <= k < j }似乎不太一樣临谱，但有一個相似點是他也要枚舉最優(yōu)的決策璃俗，這個時候有一個技巧就是，我們把決策表打印出來悉默，看他是不是每行單調(diào)遞增(允許>=）城豁，同時每列也單調(diào)遞增(允許>=）。如果滿足這個性質(zhì)抄课，大概率這個式子也是滿足決策單調(diào)性唱星，就可以用四邊形不等式的套路進行優(yōu)化
所以基礎(chǔ)代碼如下

int inf = Integer.MAX_VALUE / 2;
private int[][] dis(int[] a) {
    int l = a.length;
    int[][] dis = new int[l][l];
    for (int i = 0; i < l; i++) {
        for (int j = i + 1; j < l; j++) {
            dis[i][j] = dis[i][j - 1] + a[j] - a[(j + i)/2];
        }
    }
    return dis;
}
public int minDistance(int[] houses, int k) {
    Arrays.sort(houses);
    int[][] dis = dis(houses);
    int n = houses.length;
// DP I J 表示前J個屋子用了I個郵局的最小距離和
    int[][] dp = new int[k + 1][n];
    int[][] s = new int[n+1][n+1];
    for (int[] i : s) Arrays.fill(i, -1);
    for (int i = 0; i < n; i++) {
        dp[1][i] = dis[0][i];
    }
    for (int l = 2; l <= k; l++) {
        for (int i = l; i < n; i++) {
            dp[l][i] = inf;
            for (int j = l-1; j <= i; j++) { // 枚舉最后一個郵局COVER 多少房子
                if (dp[l - 1][j - 1] + dis[j][i] < dp[l][i]) {
                    dp[l][i] = dp[l - 1][j - 1] + dis[j][i];
                    s[l][i] = j; 
                }
            }
        }
    }
    // 驗證行單調(diào)
    for (int[] i : s) {
        boolean seeingMinusOne = true;
        for (int j = 1; j < i.length; j++) {
            if (seeingMinusOne && i[j-1] != -1) seeingMinusOne = false;
            if (i[j] == -1 && !seeingMinusOne ) i[j] = inf;
            assert i[j] >= i[j-1];

        }
    }
    // 驗證列單調(diào)
    for (int i = 0; i < n; i++) {
        boolean seeingMinusOne = true;
        for (int j = 1; j < n; j++) {
            if (seeingMinusOne && s[j-1][i] != -1) seeingMinusOne = false;
            if (s[j][i] == -1 && !seeingMinusOne ) s[j][i] = inf;
            assert s[j][i] >= s[j-1][i];
        }
    }
    return dp[k][n - 1];
}

用這個代碼去跑一下評測系統(tǒng)，如果出現(xiàn)ASSERTION ERROR跟磨，那么就代表決策不具備單調(diào)性间聊，如果沒出問題，那么我們可以去嘗試用四邊形不等式優(yōu)化抵拘。

下面我就是要思考這里我們要算的是DP[L][I]哎榴，那么更新的決策點就是S[L][I]，這個時候S[L-1][I] 是已經(jīng)求好了僵蛛，另外一側(cè)需要S[L][I+1]尚蝌，那么就需要第二層循環(huán)從大到小，再檢查一下DP只需要上一層的元素充尉，所以從大到小是沒問題的飘言。

因為I都是從I-1開始，那么初始的第三層循環(huán)的右側(cè)<=值最大應(yīng)該是N-1喉酌，所以S[L][N] = N - 1.同時因為L是從2開始的热凹，我們需要構(gòu)建好左邊的初始值，S[1][i] = 1. (因為L =2 , 然后J從L-1開始泪电，所以=1)

用四邊形不等式優(yōu)化的代碼如下：

int inf = Integer.MAX_VALUE / 2;
private int[][] dis(int[] a) {
    int l = a.length;
    int[][] dis = new int[l][l];
    for (int i = 0; i < l; i++) {
        for (int j = i + 1; j < l; j++) {
            dis[i][j] = dis[i][j - 1] + a[j] - a[(j + i)/2];
        }
    }
    return dis;
}
public int minDistance(int[] houses, int k) {
    Arrays.sort(houses);
    int[][] dis = dis(houses);
    int n = houses.length;
    int[][] dp = new int[k + 1][n];
    int[][] s = new int[n+1][n+1];  // step.1 
    for (int[] i : s) Arrays.fill(i, -1);
    for (int i = 0; i < n; i++) {
        dp[1][i] = dis[0][i];
        s[1][i] = 1; // step 4.
    }
    
    for (int l = 2; l <= k; l++) {
        s[l][n] = n - 1; // step 4.
        for (int i = n - 1; i >= l - 1; i--) {
            dp[l][i] = inf;
            int st = s[l-1][i], ed = s[l][i+1]; // step 3.
            for (int j = st; j <= ed; j++) {
                if (dp[l - 1][j - 1] + dis[j][i] < dp[l][i]) {
                    dp[l][i] = dp[l - 1][j - 1] + dis[j][i];
                    s[l][i] = j; // step 2.
                }
            }
        }
    }
    
    return dp[k][n - 1];
}

到這里我已經(jīng)把四邊形不等式如何優(yōu)化的思想已經(jīng)介紹完了般妙，當(dāng)然四邊形不等式的優(yōu)化還可以運用再一維DP里，不過本文已經(jīng)相當(dāng)長了相速。而且我還有斜率優(yōu)化也還沒寫碟渺，所以我們1維DP的四邊形不等式優(yōu)化和斜率優(yōu)化放在下一章講。因為這2個算法突诬，目前LC還沒有對應(yīng)的題目苫拍，所以算是超綱講授。不過既然都開始寫了旺隙，就寫寫完完整整绒极。所以小伙伴們，我們下章見蔬捷。

總結(jié)

這次我們主要學(xué)習(xí)了矩陣快速冪來優(yōu)化基于狀態(tài)機轉(zhuǎn)移的DP計數(shù)類問題垄提。原理就是把初始狀態(tài)設(shè)計成向量榔袋，轉(zhuǎn)移方程設(shè)計為矩陣。轉(zhuǎn)移過程就是向量和矩陣的乘法铡俐，然后因為矩陣乘法具有結(jié)合律凰兑，所以我們可以先算矩陣乘法通過快速冪的方式達到優(yōu)化效果。

隨后是四邊形不等式的優(yōu)化审丘，原理就是在區(qū)間類DP中需要枚舉最優(yōu)決策點時吏够，我們可以通過判斷代價函數(shù)是否滿足區(qū)間包含單調(diào)性，和四邊形不等式來得知決策點是否具備單調(diào)性滩报，如果具備單調(diào)性就可以用4步法來把O(N^3)的復(fù)雜度優(yōu)化至 O (N^2）锅知。

老慣例，給大家留2道思考題脓钾。

在矩陣快速冪中喉镰，那道同學(xué)上課缺席遲到的題目，如果L和A是動態(tài)傳入惭笑，應(yīng)該如何通過代碼來構(gòu)建轉(zhuǎn)移矩陣呢？

石子合并那道題生真，如果是求最大COST沉噩，應(yīng)該怎么做呢？

請研究https://leetcode.com/problems/minimum-cost-to-merge-stones/ 怎么做柱蟀，能否用四邊形不等式川蒙。

上期思考題時間

在一棵有根多叉樹中，如何使用二進制優(yōu)化长已，來找最近公共祖先呢畜眨？

這道題分為3步。

第一步术瓮，同樣我們對這顆樹的每個節(jié)點構(gòu)建工具包康聂，使得每個節(jié)點向上的一步，二步胞四，四步恬汁。。辜伟。的節(jié)點編號都直接被存下來氓侧。同時把每個節(jié)點的深度給存下來。

隨后深度深的那個節(jié)點导狡，開始從大工具（步數(shù)大的開始跳）開始使用约巷，使用的前提是用完之后，依然沒有比深度淺的節(jié)點更淺旱捧。那么就用独郎，繼續(xù)換小工具。這樣做的目標(biāo)是使得2個節(jié)點在同一深度。

隨后如果2個節(jié)點是一個點了囚聚，那么就直接返回靖榕。如果不是，就來到第三步顽铸。

第三步就是2個節(jié)點使用工具一起往上跳茁计，用該工具的前提是，2個節(jié)點用完不會使得他們來到了同一個節(jié)點（因為可能跳過頭了）谓松；我們的目標(biāo)要找到最淺的一個不同的父節(jié)點星压，那么他們上面一個就是最近公共祖先。

總共有 n 道題目要抄鬼譬，編號 0,1,…,n娜膘，抄第 i 題要花 ai 分鐘。老師要求最多可以連續(xù)空的題為K优质，求消耗時間最少滿足老師要求的方案竣贪。

首先我們可以在最后加1個時間為0 的題。然后這樣就可以用DP[N+1]來得到答案巩螃。

DP[N+1]表示的是N+1這道題寫了的話花的最小時間演怎。

隨后我們就可以知道轉(zhuǎn)移方程就是，因為最多K道空避乏，那么前K道里面必然需要一個題是寫的爷耀，那么就從這K個DP轉(zhuǎn)移過來，求最小拍皮。那么這里也是維護區(qū)間最小值歹叮，我們可以用單調(diào)隊列來解決。

DP的五類優(yōu)化(2) - 快速冪暇韧，四邊形不等式

DP的五類優(yōu)化(2) - 快速冪勾习，四邊形不等式

斐波那契數(shù)列

另一道LEETCODE

什么樣的問題可以用矩陣快速冪優(yōu)化

四邊形不等式優(yōu)化

優(yōu)化之后的代碼會長這樣

我們再來研究下這個優(yōu)化到底在遍歷什么棋傍？

我們再來看一道這周周賽的一個問題

總結(jié)

上期思考題時間

在一棵有根多叉樹中，如何使用二進制優(yōu)化长已，來找最近公共祖先呢畜眨？

總共有 n 道題目要抄鬼譬，編號 0,1,…,n娜膘，抄第 i 題要花 ai 分鐘。老師要求最多可以連續(xù)空的題為K优质，求消耗時間最少滿足老師要求的方案竣贪。