在上一章中，我們介紹了基于單調(diào)隊(duì)列和二進(jìn)制DP的優(yōu)化。
今天我們來看另外3類，斜率優(yōu)化，四邊形不等式，快速冪優(yōu)化。
斐波那契數(shù)列
一般大學(xué)的DP課，都會(huì)從這個(gè)有名的數(shù)列講起。通常會(huì)給你們演示的遞歸寫法，發(fā)現(xiàn)在算接近40的菲波那切項(xiàng)的時(shí)候就長時(shí)間返回不出值了。這種做法被證明是指數(shù)級(jí)的復(fù)雜度。隨后便開始講解遞歸過程中，比如F(K) 在很多遞歸樹的分支里都被展開進(jìn)行了重復(fù)計(jì)算。如果我們可以保存一個(gè)已經(jīng)算好的結(jié)果，之后相同K的計(jì)算其實(shí)是可以復(fù)用之前這個(gè)算好的結(jié)果的。這就是記憶化搜索，也稱自頂向下的DP。這種做法可以把原來的指數(shù)級(jí)別的時(shí)間復(fù)雜度給優(yōu)化到線性的。
其實(shí)這個(gè)數(shù)列還可以更快，這里就要用到矩陣乘法的思想了。在講這個(gè)之前，我們先來介紹一下快速冪是什么？
我們來看一道LEETCODE的題目
https://leetcode.com/problems/powx-n/
我們?cè)谒鉞 的 N次方時(shí)，最基本的做法是X 乘以N次。其實(shí)我們也可以用二進(jìn)制的思想來用LOG N 的時(shí)間把它算出來。
比如我們算4次方，我們可以用X^2 的結(jié)果 直接 再平方。 同理算8次方的話，我們可以先把x^2 給算好，接下來只要算x^2 的四次方了。 然后我們把x^4算好，只要算它的平方了。
那么如果是奇數(shù)怎么辦，我們可以把當(dāng)前的值預(yù)先乘進(jìn)答案里來解決。比如三次方我們發(fā)現(xiàn)是奇數(shù)，我們可以先把X 乘一次到答案，然后再算X^2即可。
所以會(huì)有如下代碼
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ù)，把答案先乘進(jìn)結(jié)果
p = p * p; // 把x 的基礎(chǔ) 變成 x^2
n >>= 1; // 之后只需要求原來的一半次冪
}
return res;
}
上述是快速冪的基本思想。這里假設(shè)小伙伴們已經(jīng)知道了矩陣乘法是如何做的。以及1個(gè) M * N 的矩陣 乘以 一個(gè) N * K的矩陣 結(jié)果是 M * K的矩陣。如果不知道的，可以看我的這篇博客或上網(wǎng)查閱資料。
博客里也介紹了 只有方陣 才有矩陣的冪。
那么矩陣乘法快速冪的DP優(yōu)化的核心思想如下：
一組DP狀態(tài)，其實(shí)等價(jià)于一個(gè)向量。而DP狀態(tài)的轉(zhuǎn)移方程，可以是對(duì)一個(gè)向量做變形的矩陣。那么本質(zhì)上從1個(gè)向量到另一個(gè)狀態(tài)的向量，是可以通過一個(gè)矩陣來做到。矩陣具有結(jié)合律，我們可以先對(duì)右半部分矩陣用快速冪得到一個(gè)終極的變形矩陣，再乘以向量，就可以把O(N)的計(jì)算 優(yōu)化到 O (LOG (N))
第一次接觸這個(gè)思想的小伙伴一定會(huì)覺得非常陌生，不過我們就拿斐波那契數(shù)列來下手。
我們可以知道斐波那契的遞推公式為 dp[i] = dp[i-1] + dp[i - 2]; 那么每一個(gè)新的數(shù)的計(jì)算依賴于前2個(gè)，所以我們結(jié)果可以構(gòu)建這么一個(gè)向量為 【dp[n], dp[n-1]】
那么怎么轉(zhuǎn)移呢，其實(shí)就是找用什么樣的矩陣和這個(gè)向量做乘法后，可以讓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]】這個(gè)矩陣對(duì)向量【dp[n], dp[n-1]】做乘法即可得到【dp[n+1], dp[n]】。
那么有了上述公式， 如果要從 dp[1], dp[2] 求到 dp[n], dp[n-1] 中間需要有N-2個(gè)同樣的變形矩陣的乘法。
綜上我們可以實(shí)現(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/
這道題主要是講馬子跳躍法，然后再一個(gè)鍵盤上可能打出多少不同的數(shù)字，在跳N步之后。比如跳1步，那么就是10. 因?yàn)榈谝粋€(gè)鍵可以按在任何一個(gè)位置。跳2步，是20.
這道題可以直接TOP DOWN去做，比如我的目標(biāo)是最后在1這個(gè)位置，跳完K步。那么能跳到1 的，只有
我們這里定K=2,也就是求跳完2步的數(shù)量
所以就有 dfs(1, K=2） = dfs (6, K=1) +dfs(8, K=1)
K = 1 是遞歸出口，返回1就好了。
有了這個(gè)思路，我們其實(shí)只要把每個(gè)點(diǎn)可以由哪些點(diǎn)跳過來的信息保存好。
就可以搜索了。
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),
}
因?yàn)榈竭_(dá)一個(gè)點(diǎn)之后K步，和之前怎么跳過來的是不相關(guān)的。所以我們可以人為無論前面怎么跳，你現(xiàn)在跳到了M的數(shù)字，并且還有K步，余下到1的可能性都是不變的。那么就可以引入記憶化搜索來避免重復(fù)的遞歸展開計(jì)算。這樣時(shí)間復(fù)雜度就是狀態(tài)數(shù)量 * 每次遞歸函數(shù)要做的操作。 狀態(tài)數(shù)量是 10 * K（K為跳的步數(shù)）
其實(shí)這道題就解決了。
其實(shí)我們可以發(fā)現(xiàn)這道題也是當(dāng)前的狀態(tài)是通過上一步的狀態(tài)，根據(jù)固定的公式去轉(zhuǎn)移的，最后是去求個(gè)數(shù)，我們就可以使用矩陣來為向量做變換的思想把它優(yōu)化到LOG (N)。
上面這個(gè)鄰居信息表的含義其實(shí)就是dp[i][1] = dp[i-1][4] + dp[i-1][6];
那么我們把需要的位置給設(shè)置成系數(shù)1， 不需要的位置設(shè)置成系數(shù)0，上面的MAP等價(jià)于下面的矩陣
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的值求和即可。
如果理解的斐波那契那里的代碼，下面其實(shí)是一樣一樣的。
注意因?yàn)橄蛄渴切邢蛄?，所以做乘法的時(shí)候，是和矩陣的列去乘，所以上面的MAP，再轉(zhuǎn)矩陣的時(shí)候，應(yīng)該從行映射到矩陣的列。比如上面的MAP的第一行其實(shí)等價(jià)下面矩陣的第一列。當(dāng)然你定義初始向量為列向量，就可以不用做這個(gè)變換。
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)這里有個(gè)狀態(tài)機(jī)轉(zhuǎn)化的思想，我們把它寫成矩陣和向量的乘法形式，這類DP都可以使用快速冪; 當(dāng)然這種題目會(huì)要求去求個(gè)數(shù)，而不是MIN/ MAX
但并不是只要是狀態(tài)機(jī)變化的計(jì)數(shù)DP都可以用矩陣乘法快速冪。比如經(jīng)典的DECODE ways，https://leetcode.com/problems/decode-ways/
雖然他是從DP[N-1] 和 DP[N-2] 過來，但是里面涉及到了條件分支，這種題目無法寫成矩陣變換的形式。
下面我們?cè)倏匆坏揽梢杂每焖賰绲乃枷肴ソ獾念}，然后看我們?cè)趺炊x不同的狀態(tài)使得可以用不同的矩陣轉(zhuǎn)換來表示的情況。
https://leetcode.com/problems/student-attendance-record-ii/
題目中要求一個(gè)學(xué)生最多只能出現(xiàn)1個(gè)A， 和2個(gè)連續(xù)的L（也就是說不要求L的總數(shù)，只要沒有3個(gè)連續(xù)的L即可）
同時(shí)我們發(fā)現(xiàn)這道題也是求個(gè)數(shù)，我們可以之后思考是否可以用快速冪來優(yōu)化。
我們看怎么來定義DP的狀態(tài)。首先A和L一定會(huì)在狀態(tài)機(jī)里的。不可以定dp[n][i][j] 表示第N天時(shí)，這個(gè)學(xué)生已經(jīng)連續(xù)i天是L了，且歷史上發(fā)生了j次A
那么根據(jù)這個(gè)狀態(tài)，我們可以知道如果i >0 那么其實(shí)只能從dp[n-1][i-1][j]轉(zhuǎn)移過來，因?yàn)槟阆ＭB續(xù)2天是L，必然要從連續(xù)1天是L轉(zhuǎn)過來。
如果i = 0的時(shí)候，可以從其他所有狀態(tài)轉(zhuǎn)過來，因?yàn)橹灰俳Y(jié)尾加個(gè)P或加個(gè)A，就可以破壞掉連續(xù)i天是L的連續(xù)。根據(jù)這個(gè)思路，我們也可以列出關(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)換成矩陣。這里我們要對(duì)I,J 做編碼。因?yàn)镴最多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é)尾的個(gè)數(shù)做一個(gè)求和即是題目的答案
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);
}
我們?cè)賮砜匆粋€(gè)狀態(tài)的表示方法，之前我們定義的是結(jié)尾有多少個(gè)L。這里我們可以定義結(jié)尾最多可能有多少個(gè)L。這樣定義的好處是最后不用作那個(gè)求和。因?yàn)槲覀兊臓顟B(tài)是最多有多2個(gè)L，所以也包含了1個(gè)L和0個(gè)L的情況了。為了把A也給不求和，所以我們把狀態(tài)也轉(zhuǎn)成歷史上最多有了多少個(gè)A
這樣我們最后只要返回dp[n][2][1] 就是所有結(jié)果。
那么因?yàn)槎几臑樽疃?，所以第一個(gè)變化的就是初始向量，原來除了0,0 其他都不合法?，F(xiàn)在因?yàn)槭亲疃?，也就是L和A可有可無。所以求變得全合法了。
long[][] res = new long[][]{{1,1,1,1,1,1}};
然后狀態(tài)轉(zhuǎn)移是如何呢，我們知道0,0 現(xiàn)在只能從前一個(gè)2,0過來了，不然就破壞了最多的定義。因?yàn)橹灰右粋€(gè)P，就可以使得結(jié)尾最多又恢復(fù)到0個(gè)L。
1,0 也可以從2,0轉(zhuǎn)過來（通過最后加P）
也可以從（0,0）轉(zhuǎn)過來，通過最后加L。 但是不能最后加A，因?yàn)楫?dāng)前定義是歷史上最多0個(gè)A。（注意歷史上最多和只看結(jié)尾上最多還是有區(qū)別的）
所以我們發(fā)現(xiàn)任何狀態(tài)都可以從（0,2）轉(zhuǎn)過來，因?yàn)樽詈蠖伎梢约覲。
只有當(dāng)I >0時(shí)，可以從（i-1， x)轉(zhuǎn)過來，通過加L, 注意這里的X和上一個(gè)狀態(tài)要一致，因?yàn)檫@里是歷史上最多。
當(dāng)J >0，可以從（2， j -1)轉(zhuǎn)過來, 通過加A。這里前面可以直接取最大值2，因?yàn)榧恿艘粋€(gè)A我們就不會(huì)讓最多2個(gè)L的性質(zhì)不合法，所以可以取2.
那么下面就是寫轉(zhuǎn)移矩陣了。因?yà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
下面只要改一下初始矩陣，和變換矩陣，其余代碼不用動(dòng)，最后直接返回即可。
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)化的思想，就是把計(jì)數(shù)的狀態(tài)機(jī)轉(zhuǎn)換的DP，通過把初始狀態(tài)表示為初始向量，轉(zhuǎn)移方程表示為變換矩陣。通過矩陣快速冪的方式優(yōu)化時(shí)間復(fù)雜度從O(n) 到 O(log(n))的一類技巧。
講到這里矩陣快速冪優(yōu)化就要告一段落，再開始新的篇章前，我給你們留一道思考題。
上題中L和A 都是定值，如果L和A，是可變的（假設(shè)2者之和不超過10）,你該如何實(shí)現(xiàn)LOG N的算法呢？
四邊形不等式優(yōu)化
四邊形不等式DP理論非常復(fù)雜，編碼還是比較簡單。
先說下他的由來。我們都知道一個(gè)東西叫最優(yōu)樹。還記得我們?cè)趯W(xué)編碼時(shí)的哈夫曼數(shù)嗎，因?yàn)槊總€(gè)字母的出現(xiàn)頻率不一樣，所以我們希望頻率高的編碼盡可能短，就有了哈夫曼樹的思想。他就是貪心的去合并權(quán)值最小的2個(gè)樹，最后合到一顆為止。該樹即為所求的哈夫曼樹。
隨后計(jì)算機(jī)鼻祖 高納德 在解決最優(yōu)二叉搜索樹時(shí)發(fā)明的一個(gè)算法，隨后姚期智的夫人，做了深入研究，擴(kuò)展為一般性的DP優(yōu)化方法?？梢园岩恍r(shí)間復(fù)雜度O(n3)的DP問題優(yōu)化到O(n2), 所以這個(gè)方法又被成為 (Knuth-Yao speedup theorem)
最優(yōu)二叉搜索樹問題：
現(xiàn)有 n 個(gè)排序過的數(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ù)這些概率組成一個(gè)高效的二叉搜索樹，使得每次搜索的平均時(shí)間最小化。只需要返回該樹的最優(yōu)平均時(shí)間，不需要表達(dá)或者返回樹的結(jié)構(gòu)。
我們來思考下因?yàn)槎嫠阉鳂湫枰３止?jié)點(diǎn)本身有序的特性，所以我們不能像哈夫曼樹那樣貪心的取2個(gè)概率最小的子樹去合并，因?yàn)闀?huì)破壞搜索樹的特性。其實(shí)這里等價(jià)于只有相鄰的子樹可以合并。這樣我們可以把最小的子問題給求好，然后依據(jù)最小求次小。次小的時(shí)候我們需要枚舉決策點(diǎn)，然后再所有決策點(diǎn)里找最小。這樣的做法是O(n^3)的。
因?yàn)橐闅vN層，每一層我們要遍歷N個(gè)窗口，每個(gè)窗口我們又要枚舉最優(yōu)決策點(diǎn)。
我們來看下N^3的代碼如實(shí)寫
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é)點(diǎn)數(shù)為LEN的子樹的最優(yōu)解
for (int i = 1; i < n + 1 - len; i++) { // 滑動(dòng)每一個(gè)窗口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++) { // 枚舉決策點(diǎn),K是根節(jié)點(diǎn)
if (dp[i][j] > dp[i][k-1] + dp[k+1][j]) {
dp[i][j] = dp[i][k-1] + dp[k+1][j]; // 左右子樹的搜索代價(jià)各加一層
}
}
dp[i][j] += subTreeProbabilitySum[i][j]; // 有這個(gè)樹的搜索代價(jià)加一層
}
}
return dp[1][n - 1];
}
上面的代碼我們可以跑2個(gè)簡單的例子論證下正確性
比如，只含一個(gè)節(jié)點(diǎn)的樹，他的最優(yōu)解就是本身，但是左右的GAP 因?yàn)樵诒闅v的時(shí)候是需要搜到NULL節(jié)點(diǎn)才能確定這個(gè)值不存在，所以搜的層數(shù)都為2.
Assert.assertTrue(0.2 + (0.3 + 0.5) * 2 ==
calculateOptimalBST(new double[]{-1, 0.2}, new double[]{0.3, 0.5}));
我們?cè)賮眚?yàn)證2個(gè)節(jié)點(diǎn)的情況，加入第一個(gè)GAP區(qū)間概率很高，我們應(yīng)該拿左邊的節(jié)點(diǎn)為根節(jié)點(diǎn)更優(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}));
我們?cè)賮眚?yàn)證2個(gè)節(jié)點(diǎn)的情況，加入最后一個(gè)GAP區(qū)間概率很高，我們應(yīng)該拿右邊的節(jié)點(diǎn)為根節(jié)點(diǎn)更優(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)化。
這個(gè)優(yōu)化的證明過程非常繁瑣，我這里只講技巧，具體證明我給大家一些不錯(cuò)的資料，有興趣的朋友大家可以根據(jù)資料去學(xué)習(xí)。比如B站的這個(gè)視頻
這類的優(yōu)化過程通常是這樣的，比如原來的O（N^3）的寫法是這樣
優(yōu)化之后的代碼會(huì)長這樣
上面我們引入一個(gè)關(guān)鍵的S表，他代表我們之前求過的最優(yōu)決策。
這個(gè)決策表會(huì)有一些初始值我們需要賦值，之后就是用最優(yōu)決策來鎖定第三層循環(huán)的范圍。被證明可以讓第三層在第二層下的總次數(shù)是O （N）的。 也就是表面上看是2層循環(huán)，但是實(shí)際只有O（N）的遍歷次數(shù)，具體可以通過打CNT，每遍歷一次
CNT++來直觀感受。
下面我們來分析什么時(shí)候可以用四邊形不等式。
1、如果上述的w函數(shù)同時(shí)滿足區(qū)間包含單調(diào)性和四邊形不等式性質(zhì)，那么函數(shù)dp也滿足四邊形不等式性質(zhì)
我們?cè)俣xs(i,j)表示 dp(i,j) 取得最優(yōu)值時(shí)對(duì)應(yīng)的下標(biāo)（即 i≤k≤j 時(shí)，k 處的 dp 值最大，則 s(i,j)=k此時(shí)有如下定理
2、假如dp(i,j)滿足四邊形不等式，那么s(i,j)單調(diào)，即 s(i,j)≤s(i,j+1)≤s(i+1,j+1)
所以也就是說只要W函數(shù)，有2個(gè)性質(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)性 ：如果對(duì)于任意 a<=b<=c<=d ，均有w(b,c) <= w(a,d) 成立，則稱函數(shù) w 對(duì)于區(qū)間包含關(guān)系具有單調(diào)性。
- 四邊形不等式 ：如果對(duì)于任意 a <= b <= c <= d ，均有 w(a,c) + w(b,d) <= w(a,d) + w(b,c) 成立，則稱函數(shù) 滿足四邊形不等式（簡記為“交叉小于包含”）。若等號(hào)永遠(yuǎn)成立，則稱函數(shù) w 滿足 四邊形恒等式 。
我們回過頭來看上面最優(yōu)二叉搜索樹的W函數(shù)。
本質(zhì)上是subTreeProbabilitySum， 因?yàn)榧拥亩际?gt;=0很容易得出大區(qū)間一定>=小區(qū)間，所以滿足區(qū)間包含單調(diào)性
第二個(gè)四邊形不等式，有時(shí)可以直接證明出來是滿足的，有些時(shí)候不太好想，我們可以直接對(duì)W函數(shù)打表，然后驗(yàn)證所有的ABCD，如果是滿足的。那么大概率可以用四邊形不等式優(yōu)化。
我們來寫個(gè)打表函數(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;
}
}
}
}
如果沒有報(bào)錯(cuò)，我們可以嘗試用一下四邊形不等式優(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步。
- 第一步，引入決策表。
- 第二步，在更新時(shí)更新決策表。
- 第三步，在第三層循環(huán)時(shí)，用決策表的數(shù)據(jù)來循環(huán)。
- 第四步，是需要思考的，如何賦初始值。這道題因?yàn)樽铋_始算的是DP[I][I]， 也就是1的單位，那么對(duì)S[I][j]來說，他的前驅(qū)和后繼s[i][j-1] 和 s[i+1][j] 都是0 的單位，所以要在賦初始值時(shí)用s[i][i-1]，其次就是在第一次循環(huán)時(shí)ed 這個(gè)位置因?yàn)橹挥幸粋€(gè)長度好遍歷，所以這里要加個(gè)MIN
我們?cè)賮硌芯肯逻@個(gè)優(yōu)化到底在遍歷什么？
首先我們會(huì)發(fā)現(xiàn)，他是根據(jù)長度從小到大在遍歷每個(gè)窗口。在每層長度中，每個(gè)窗口要遍歷的范圍則是S[i][j-1] 到 S[i+1][j]. 具體一下再LEN=1, I = 1時(shí)，其實(shí)就是 s[2][1] - s[1][0] 個(gè)決策點(diǎn). 隨后I到2了，變成s[3][2] - s[2][1] 個(gè)決策點(diǎn)。 那么發(fā)現(xiàn)前項(xiàng)和后項(xiàng)有正負(fù)號(hào)可以抵消。所以最終一個(gè)LEN的遍歷次數(shù)就是 s[n-1][n-len+1] - s[len-1][0]。根據(jù)S數(shù)組的定義，就是決策點(diǎn)，所有決策定都不會(huì)超過N，所以對(duì)于一個(gè)LEN來說，內(nèi)部2個(gè)循環(huán)和為s[n-1][n-len+1] - s[len-1][0] <= n.
就證明是O(n ^ 2) 了
我們可以看一道類似的題目
https://www.lintcode.com/problem/stone-game
這道題其實(shí)和最優(yōu)二叉樹還是比較像的，區(qū)別就是不用考慮GAP區(qū)間。其實(shí)也就更加簡單。
因?yàn)椴豢紤]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]
這樣變形之后帶入原式，就會(huì)發(fā)現(xiàn)左右兩邊相等。
另外一個(gè)最優(yōu)二叉搜索樹的DP[I,J] 其實(shí)是包含了gap[i-1] ~gap[j] 的。
所以枚舉最優(yōu)決策不讓左右最優(yōu)子樹的GAP有重疊需要從dp[i][k-1] 和 dp[k+1][j]來轉(zhuǎn)移。因?yàn)樗麄兇砹薵ap[i-1]~gap[k-1] 和 gap[k]~gap[j]的2顆最優(yōu)子樹。剛好排除了決策節(jié)點(diǎn)的全覆蓋。
而這道題因?yàn)椴淮嬖贕AP，DP[I,J]的定義也發(fā)生了變化，指的是合并stone[i] ~ stone[j], 所以枚舉K的時(shí)候，是dp[i][k] 和 dp[k+1][j]轉(zhuǎn)移過來，意思是最后是由[i,k]這堆石頭和[k+1, j]這堆石頭合并。
我們來看下直接用四邊形，因?yàn)槭舆@個(gè)問題，循環(huán)是從長度為2的情況開始（1是終態(tài)不用算的），所以在初始化的時(shí)候是初始化1，而不是像上一題初始化0.這些都是要注意的細(xì)節(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í)
我們?cè)賮砜匆坏肋@周周賽的一個(gè)問題
https://leetcode.com/problems/allocate-mailboxes/
這道題暴力的思路是，我們只分析前K個(gè)房子，假設(shè)此時(shí)要建M個(gè)郵局。我們已經(jīng)知道M-1個(gè)郵局，前0~K-1個(gè)房子下的最優(yōu)解。我們只要枚舉最后一個(gè)郵局建造的位置管轄的屋子，然后不管轄的屋子靠前面算過的最優(yōu)子問題直接獲得答案即可得到當(dāng)前問題的答案。
因?yàn)檫@里最優(yōu)子問題是由2個(gè)維度組成N和K。那么枚舉決策的時(shí)候還是要根據(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個(gè)村莊建j個(gè)郵局的最小距離和，k枚舉1到i的所有村莊；w[k+1][i]表示第k+1個(gè)村莊到第i個(gè)村莊建一個(gè)郵局的最小距離和，有一個(gè)顯然的性質(zhì)：在某一段區(qū)間上建一個(gè)郵局，最小距離和為在其中點(diǎn)村莊上建
那么我先來思考怎么快速的把這個(gè)W數(shù)組給求出來
我們知道如果只有一個(gè)房子w[i][i] = 0.
如果有2個(gè)房子，我們是取中點(diǎn)建是最優(yōu)的。所以我們新加了一個(gè)房子就是加上他到中點(diǎn)的距離。
int mid=(i+j)/2;
w[i][j] = w[i][j-1]+abs(x[j]-x[mid]);
有讀者可能會(huì)問，除了最后一個(gè)點(diǎn)不算，為什么w[i][j] = w[i][j-1]，中點(diǎn)不是會(huì)隨著加了一個(gè)屋子，而往后移嗎？
這個(gè)我們可以分類討論看，如果是從奇數(shù)房子增加到偶數(shù)房子。中點(diǎn)是不會(huì)移動(dòng)的，所以可以等價(jià)。
如果是偶數(shù)房子增加到奇數(shù)房子，中點(diǎn)是需要往后移動(dòng)一格。但是原來小于等于中點(diǎn)的房子數(shù)量是偶數(shù)的一半，我把中點(diǎn)往后移，這一半的房子的距離都要加上中點(diǎn)移動(dòng)的距離。同時(shí)剩下一半的房子的距離都會(huì)減去中點(diǎn)移動(dòng)的距離。因?yàn)?半的房子數(shù)量相同，所以值還是不變的。綜上這個(gè)等式是成立的。
那么我們就可以在O(N ^ 2） 的時(shí)間求完W數(shù)組
接下來主要的時(shí)間瓶頸就是DP這個(gè)O(n * n * K)的復(fù)雜度。
這個(gè)式子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 }似乎不太一樣，但有一個(gè)相似點(diǎn)是他也要枚舉最優(yōu)的決策，這個(gè)時(shí)候有一個(gè)技巧就是，我們把決策表打印出來，看他是不是每行單調(diào)遞增(允許>=），同時(shí)每列也單調(diào)遞增(允許>=）。如果滿足這個(gè)性質(zhì)，大概率這個(gè)式子也是滿足決策單調(diào)性，就可以用四邊形不等式的套路進(jìn)行優(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個(gè)屋子用了I個(gè)郵局的最小距離和
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++) { // 枚舉最后一個(gè)郵局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;
}
}
}
}
// 驗(yàn)證行單調(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];
}
}
// 驗(yàn)證列單調(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];
}
用這個(gè)代碼去跑一下評(píng)測系統(tǒng)，如果出現(xiàn)ASSERTION ERROR，那么就代表決策不具備單調(diào)性，如果沒出問題，那么我們可以去嘗試用四邊形不等式優(yōu)化。
下面我就是要思考這里我們要算的是DP[L][I]， 那么更新的決策點(diǎn)就是S[L][I]，這個(gè)時(shí)候S[L-1][I] 是已經(jīng)求好了，另外一側(cè)需要S[L][I+1]， 那么就需要第二層循環(huán)從大到小，再檢查一下DP只需要上一層的元素，所以從大到小是沒問題的。
因?yàn)镮都是從I-1開始，那么初始的第三層循環(huán)的右側(cè)<=值最大應(yīng)該是N-1，所以S[L][N] = N - 1.同時(shí)因?yàn)長是從2開始的，我們需要構(gòu)建好左邊的初始值，S[1][i] = 1. (因?yàn)長 =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)化還可以運(yùn)用再一維DP里，不過本文已經(jīng)相當(dāng)長了。而且我還有斜率優(yōu)化也還沒寫，所以我們1維DP的四邊形不等式優(yōu)化和斜率優(yōu)化放在下一章講。因?yàn)檫@2個(gè)算法，目前LC還沒有對(duì)應(yīng)的題目，所以算是超綱講授。不過既然都開始寫了，就寫寫完完整整。所以小伙伴們，我們下章見。
總結(jié)
這次我們主要學(xué)習(xí)了矩陣快速冪來優(yōu)化基于狀態(tài)機(jī)轉(zhuǎn)移的DP計(jì)數(shù)類問題。原理就是把初始狀態(tài)設(shè)計(jì)成向量，轉(zhuǎn)移方程設(shè)計(jì)為矩陣。轉(zhuǎn)移過程就是向量和矩陣的乘法，然后因?yàn)榫仃嚦朔ň哂薪Y(jié)合律，所以我們可以先算矩陣乘法通過快速冪的方式達(dá)到優(yōu)化效果。
隨后是四邊形不等式的優(yōu)化，原理就是在區(qū)間類DP中需要枚舉最優(yōu)決策點(diǎn)時(shí)，我們可以通過判斷代價(jià)函數(shù)是否滿足區(qū)間包含單調(diào)性，和四邊形不等式來得知決策點(diǎn)是否具備單調(diào)性，如果具備單調(diào)性就可以用4步法來把O(N^3)的復(fù)雜度 優(yōu)化至 O (N^2）。
老慣例，給大家留2道思考題。
- 在矩陣快速冪中，那道同學(xué)上課缺席遲到的題目，如果L和A是動(dòng)態(tài)傳入，應(yīng)該如何通過代碼來構(gòu)建轉(zhuǎn)移矩陣呢？
- 石子合并那道題，如果是求最大COST，應(yīng)該怎么做呢？
- 請(qǐng)研究https://leetcode.com/problems/minimum-cost-to-merge-stones/ 怎么做，能否用四邊形不等式。
上期思考題時(shí)間
在一棵有根多叉樹中，如何使用二進(jìn)制優(yōu)化，來找最近公共祖先呢？
這道題分為3步。
第一步，同樣我們對(duì)這顆樹的每個(gè)節(jié)點(diǎn)構(gòu)建工具包，使得每個(gè)節(jié)點(diǎn)向上的一步，二步，四步。。。的節(jié)點(diǎn)編號(hào)都直接被存下來。同時(shí)把每個(gè)節(jié)點(diǎn)的深度給存下來。
隨后深度深的那個(gè)節(jié)點(diǎn)，開始從大工具（步數(shù)大的開始跳）開始使用，使用的前提是用完之后，依然沒有比深度淺的節(jié)點(diǎn)更淺。那么就用，繼續(xù)換小工具。這樣做的目標(biāo)是使得2個(gè)節(jié)點(diǎn)在同一深度。
隨后如果2個(gè)節(jié)點(diǎn)是一個(gè)點(diǎn)了，那么就直接返回。如果不是，就來到第三步。
第三步就是2個(gè)節(jié)點(diǎn)使用工具一起往上跳，用該工具的前提是，2個(gè)節(jié)點(diǎn)用完不會(huì)使得他們來到了同一個(gè)節(jié)點(diǎn)（因?yàn)榭赡芴^頭了）；我們的目標(biāo)要找到最淺的一個(gè)不同的父節(jié)點(diǎn)，那么他們上面一個(gè)就是最近公共祖先。
總共有 n 道題目要抄，編號(hào) 0,1,…,n，抄第 i 題要花 ai 分鐘。老師要求最多可以連續(xù)空的題為K，求消耗時(shí)間最少滿足老師要求的方案。
首先我們可以在最后加1個(gè)時(shí)間為0 的題。然后這樣就可以用DP[N+1]來得到答案。
DP[N+1]表示的是N+1這道題寫了的話花的最小時(shí)間。
隨后我們就可以知道轉(zhuǎn)移方程就是，因?yàn)樽疃郖道空，那么前K道里面必然需要一個(gè)題是寫的，那么就從這K個(gè)DP轉(zhuǎn)移過來，求最小。那么這里也是維護(hù)區(qū)間最小值，我們可以用單調(diào)隊(duì)列來解決。
