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