枚舉之后再驗證性能太差？來試下動態(tài)規(guī)劃
我們經(jīng)常會遇到這樣一個問題：
多個元素之間有很多種排列組合，讓我們選出滿足某個條件的最好的那個。
比如說：
- 一個字符串可以有 n 種子串，讓我們從中選出最長的回文串。(回文串是指 abccba 這種反過來和原字符串相等的字符串)
- n 個物品之間有很多種組合方案，讓我們選出滿足滿足重量小于某個值的最大價值的組合方案
這些問題我們最容易想到的思路就是枚舉出所有的情況，然后做下驗證和比較。
比如，第一個問題：
我們可以枚舉出所有的子串，然后判斷是否是回文串，記錄下最長的那個。
第二個問題：
可以枚舉出所有的組合方案，然后驗證下是否滿足重量小于某個值，記錄下滿足條件的價值最大的方案。
這種把所有的排列組合枚舉出來，然后依次驗證和比較的思路是最容易想到的，很多問題我們都是這樣解決。
但是這樣做一些簡單場景的業(yè)務(wù)需求還行，要是數(shù)據(jù)規(guī)模一上去，立馬 gg。
為什么呢?
第一個問題的解決方案，要枚舉所有的子串，需要枚舉所有起始點和終止點坐標的坐標，然后再判斷是否是回文串。
這需要 2 重循環(huán)來枚舉子串， 1 重循環(huán)來判斷是否回文并和最大值比較。
也就是 O(n^3) 的復(fù)雜度。
而第二個問題的解決方案，需要枚舉所有的組合，每一個物品都有選與不選兩種情況，需要遞歸 n 次來計算所有的情況，也就是一共有 2^n 種情況，枚舉出的組合方式還要計算下這 m 個物品的價值的和。
也就是 O(2^n * m) 的復(fù)雜度。
這種方案來解決業(yè)務(wù)問題可以么?可以，其實很多情況下我們都用這種樸素的容易想到的思路來解決，但是數(shù)據(jù)規(guī)模一上去，這些方案就都不行了。原因見下圖：
數(shù)據(jù)規(guī)模比較大的時候，就要換時間復(fù)雜度更低的算法了。
怎么把時間復(fù)雜度降下來呢?
我們現(xiàn)在是每一個都枚舉出來然后單獨判斷的：
每一種情況都要單獨這樣來一遍，所以組合越多，復(fù)雜度越高。
能不能找到各種組合之間的規(guī)律呢，比如可以從一種情況推出另一種情況，那不就不用每次都驗證一遍了么?
比如回文串那個問題，如果我們知道了 i 和 j 是回文串，那如果前后兩個字符如果相等的話， i-1 到 j+1 不也是回文串么?
所以就可以找到這樣的推導(dǎo)關(guān)系：
- if (str[i] === str[j] && isHuiwen[i+1][j-1]) {
- isHuiwen[i][j] = true;
- }
有了這個推導(dǎo)關(guān)系之后有啥變化呢?我們根本不用枚舉出每種情況再單獨驗證了，從一個初始的情況推導(dǎo)出后面所有的情況不就行了么?
直接從結(jié)果來推導(dǎo)，這樣復(fù)雜度一下子從 O(n^3) 降低到了 O(n)。
這種找各種情況之間規(guī)律，然后從初始狀態(tài)根據(jù)狀態(tài)轉(zhuǎn)移方程推導(dǎo)出所有狀態(tài)的算法就叫做動態(tài)規(guī)劃。
背包問題如果能找到結(jié)果之間的推導(dǎo)關(guān)系，也就不用枚舉 + 驗證了，可以直接推出來。
我們試著找一下：
我們關(guān)心的是 i 件物品，可用容量為 j 的時候，最大價值是多少。
那么第 i 件物品和 i-1 件物品的關(guān)系是什么呢?就是裝與不裝。
如果可用容量 j 小于第 i 件物品的重量 w[i]，那么裝不下。
也就是
- if (j < w[i]) {
- maxValue[i][j] = maxValue[i -1][j]
- }
如果可用容量 j 大于等于第 i 件物品的重量 w[i]，那么就能裝下。
能裝下就可以分為裝與不裝兩種情況，取大的那個即可：
- if (j >= w[i]) {
- maxValue[i][j] = Math.max(maxValue[i][j - w[i]] + val[i], maxValue[i-1][j])
- }
這就是第 i 件物品與第 i-1 件物品的關(guān)系：
- if (j < w[i]) {
- maxValue[i][j] = maxValue[i -1][j]
- } else {
- maxValue[i][j] = Math.max(maxValue[i][j - w[i]] + val[i], maxValue[i-1][j])
- }
這個狀態(tài)轉(zhuǎn)移方程列出來了之后，就能從初始狀態(tài)推導(dǎo)出所有的狀態(tài)，然后取其中滿足容量 w 的 n 件物品的最大價值。
復(fù)雜度從 O(2^n * m) 降低到了 O(n * m)。
總結(jié)
當遇到從多種組合中取滿足需求的那種組合的問題時，一般的思路就是枚舉 + 驗證，但是這種思路算法復(fù)雜度很高，性能很差。
如果能找到各種組合的情況之間的推導(dǎo)關(guān)系，就可以直接推導(dǎo)出來，比如 i 到 j 的回文串和 i-1 到 j+1 的回文串之間的關(guān)系，比如 i 個物品容量為 j 的最大價值和 i-1 個物品容量為 j 的關(guān)系。
這種思路叫做動態(tài)規(guī)劃算法。
動態(tài)規(guī)劃的難點在于找 i 和 i-1 的推導(dǎo)關(guān)系，也就是列出狀態(tài)轉(zhuǎn)移方程。
一旦理清了狀態(tài)轉(zhuǎn)移方程，也就是各組合的結(jié)果(狀態(tài))之間的推導(dǎo)關(guān)系，就可以從初始狀態(tài)把后續(xù)所有狀態(tài)推導(dǎo)出來。能夠極大的降低樸素算法的復(fù)雜度，提升幾個數(shù)量級的性能。
