動態規劃，它來了

前言

大家好，我是 bigsai，好久不見，甚是想念 (天天想念)！

很久前就有小夥伴被動態規劃所折磨，確實，很多題動態規劃確實太難看出了了，甚至有的題看了題解理解起來都費勁半天。

動態規劃的範圍雖然確實是很廣很難，但是從整個動態規劃出現的頻率來看，這幾種基礎的動態規劃理解容易，學習起來壓力不大，並且出現頻率非常高。

這幾個常見的動態規劃有：連續子數組最大和，子數組的最大乘積，最長遞增子序列 (LIS)，最長公共子序列 (LCS)，最長公共子串，最長公共子串，不同子序列。

什麼是動態規劃

首先很多人問，何爲動態規劃？動態規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優化的過程。通俗一點動態規劃就是從下往上 (從前向後) 階梯型求解數值。

那麼動態規劃和遞歸有什麼區別和聯繫？

總的來說動態規劃從前向後，遞歸從後向前，兩者策略不同，並且一般動態規劃效率高於遞歸。

不過都要考慮初始狀態，上下層數據之間的聯繫。很多時候用動態規劃能解決的問題，用遞歸也能解決不過很多時候效率不高可能會用到記憶化搜索。

不太明白?

就拿求解斐波那契額數列來說，如果直接用遞歸不優化，那麼複雜度太多會進行很多重複的計算。

但是利用記憶化你可以理解爲一層緩存，將求過的值存下來下次再遇到就直接使用就可以了。

實現記憶化搜索求斐波那契代碼爲：

static long F(int n,long record[])
{
  if(n==1||n==2) {return 1;}
  if(record[n]>0)
    return record[n];
  else
    record[n]=F(n-1,record)+F(n-2,record);
  return record[n];
}
public static void main(String[] args) {
  int n=6;
  long[] record = new long[n+1];
  System.out.println(F(n,record));
}

而動態規劃的方式你可以從前往後邏輯處理，從第三個開始每個 dp 都是前兩個 dp 之和。

 public int fib(int n) {
        int dp[]=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<n+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

當然動態規劃也能有很多空間優化，有些只用一次的值，你可以用一些變量去替代。有些二維數組很大也可以用一維數組交替替代。當然動態規劃專題很大，有很多比如樹形 dp、狀壓 dp、揹包問題等等經常出現在競賽中，能力有限這裏就將一些出現筆試高頻的動態規劃！

連續子數組最大和

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，爲 6。

dp 的方法就是 O(n) 的方法。如果 dp[i] 表示以第 i 個結尾的最大序列和，而這個 dp 的狀態方程爲：

dp[0]=a[0]
dp[i]=max(dp[i-1]+a[i],a[i])

也不難解釋，如果以前一個爲截至的最大子序列和大於 0，那麼就連接本個元素，否則本個元素就自立門戶。

實現代碼爲：

public int maxSubArray(int[] nums) {
    int dp[]=new int[nums.length];
    int max=nums[0];
    dp[0]=nums[0];
    for(int i=1;i<nums.length;i++)
    {
      dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
      if(dp[i]>max)
        max=dp[i];
    }
    return max;
}

ps: 有小夥伴問那求可以不連續的數組最大和呢？你好好想想枚舉一下正的收入囊中，那個問題沒意義的。

連續子數組最大乘積

給你一個整數數組 nums ，請你找出數組中乘積最大的連續子數組（該子數組中至少包含一個數字），並返回該子數組所對應的乘積。

示例 :

輸入: [2,3,-2,4]
輸出: 6
解釋: 子數組 [2,3] 有最大乘積 6。

連續子數組的最大乘積，這也是一道經典的動態規劃問題，但是和普通動態規劃又有點小不同。

如果數據中都是非負數，對於連續數組的最大乘積，那樣處理起來和前面連續子數組最大和處理起來有些相似，要麼和前面的疊乘，要麼自立門戶。

dp[0]=nums[0]
dp[i]=max(dp[i-1]*a[i],a[i])

但是這裏面的數據會出現負數，乘以一個負數它可能從最大變成最小，並且還有負負得正就又可能變成最大了。

這時候該怎麼考慮呢？

容易，我們開兩個 dp，一個dpmax[]記錄乘積的最大值，一個dpmin[]記錄乘積的最小值。然後每次都更新 dpmax 和 dpmin 不管當前值是正數還是負數. 這樣通過這兩個數組就可以記錄乘積的絕對值最大。

動態方程也很容易

dpmax[i]=max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])
dpmin[i]=min(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])

看一個過程就能理解明白，dpmin 就是起到中間過度的作用，記錄一些可能的負極值以防備用。結果還是 dpmax 中的值。

最長遞增子序列

最長遞增子序列，也稱爲 LIS, 是出現非常高頻的動態規劃算法之一。這裏對應力扣 300

給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。

子序列是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其餘元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

輸入：nums = [0,1,0,3,2,3]
輸出：4
解釋：最長遞增子序列是 [0,1,2,3]，因此長度爲 4 。

對於最長遞增子序列，如果不考慮動態規劃的方法，使用暴力枚舉其實還是比較麻煩的，因爲你不知道遇到比前面元素大的是否要遞增。

比如 1 10 3 11 4 5，這個序列不能選取 1 10 11 而 1 3 4 5 纔是最大的，所以暴力枚舉所有情況的時間複雜度還是非常高的。

如果我們採取動態規劃的方法，創建的dp[]數組，dp[i] 表示以nums[i]結尾的最長遞增子序列，而 dp[i] 的求解方式就是枚舉 i 號前面的元素和對應結尾的最長子序列，找到一個元素值小於nums[i]並且遞增序列最長，這樣的時間複雜度爲 O(n2)。

狀態轉移方程爲：

dp[i]=max(dp[j])+1, 其中0≤j<i且num[j]<num[i]

具體流程爲：

實現代碼爲：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int dp[]=new int[nums.length];
        int maxLen=1;
        dp[0]=1;
        for(int i=1;i<nums.length;i++){
            int max=0;//統計前面 末尾數字比自己小 最長遞增子串
            for(int j=0;j<i;j++){//枚舉
                //結尾數字小於當前數字 並且長度大於記錄的最長
                if(nums[j]<nums[i]&&dp[j]>max){
                    max=dp[j];
                }
            }
            dp[i]=max+1;//前面最長 加上自己
            if(maxLen<dp[i])
                maxLen=dp[i];
        }
        return maxLen;
    }
}

不過這道題還有一個優化，可以優化成 O(nlogn) 的時間複雜度。

我們用 dp 記錄以 nums[i] 結尾的最長子序列長度, 縱觀全局，我們希望在長度一致的情況下末尾的值能夠儘量的小！

例如 2,3,9,5 …… 在前面最長的長度爲 3 我們願意拋棄 2,3,9 而全部使用 2,3,5 。也就是對於一個值，我們希望這個值能更新以它爲結尾的最長的序列的末尾值。

如果這個值更新不了最長的序列，那就嘗試更新第二長的末尾值以防待用。例如 2,3,9,5,4,5 這個序列 2,3,5 更新 2,3,9; 然後 2,3,4 更新 2,3,5 爲最長的 2,3,4,5 做鋪墊。

而這個思路的核心就是維護一個lenth[]數組，length[i] 表示長度爲 i 的子序列末尾最小值，因爲我們每次順序增加一個長度說明這個值比前面的都大 (做了充分比較)，所以這個數組也是個遞增的，遞增，那麼在鎖定位置更新最大長度序列尾值的時候可以使用二分法優化。

實現代碼爲：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int length[]=new int[nums.length];
        int len=1;
        length[0]=nums[0];
        for(int i=1;i<nums.length;i++){
            int left=0,right=len;
            while (left<right){
                int mid=left+(right-left)/2;
                if(length[mid]<nums[i]){
                    left=mid+1;
                }else {
                    right=mid;
                }
            }
            length[left]=nums[i];
            if(right==len)
                len++;        
        }
        return len;
    }
}

最長公共子序列

最長公共子序列也成爲 LCS. 出現頻率非常高！

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。

一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）後組成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。

拿 b c d d e 和 a c e e d e 舉例，其的公共子串爲 c d e。如果使用暴力，複雜度太高會直接超時，就需要使用動態規劃。兩個字符串匹配，我們設立二維dp[][]數組，dp[i][j]表示 text1 串第 i 個結尾，text2 串第 j 個結尾的最長公共子串的長度。

這裏核心就是要搞懂狀態轉移，分析dp[i][j]的轉換情況，當到達 i,j 時候：

如果text1[i]==text2[j], 因爲兩個元素都在最末尾的位置，所以一定可以匹配成功，換句話說，這個位置的鄰居 dp 值不可能大於他（最多相等）。所以這個時候就是dp[i][j]=dp[i-1][j-1] +1;

如果text1[i]!=text2[j]，就有兩種可能性，我們知道的鄰居有dp[i-1][j],dp[i][j-1]，很多人還會想到dp[i-1][j-1]這個一定比前兩個小於等於，因爲就是前面兩個子範圍嘛！所以這時就相當於末尾匹配不成，就要看看鄰居能匹配的最大值啦，此時dp[i][j]=max(dp[i][j-1],dp[i-1][j])。

所以整個狀態轉移方程爲：

dp[i][j] = dp[i-1][j-1] + 1            //text1[i]==text2[j]時
dp[i][j] = max(dp[i][j-1],dp[i-1][j])  //text1[i]!=text2[j]時

實現代碼爲：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char ch1[]=text1.toCharArray();
        char ch2[]=text2.toCharArray();
        int dp[][]=new int[ch1.length+1][ch2.length+1];
        for(int i=0;i<ch1.length;i++)
        {
            for(int j=0;j<ch2.length;j++)
            {
                if(ch1[i]==ch2[j])
                {
                    dp[i+1][j+1]=dp[i][j]+1;
                }
                else
                    dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);

            }
        }
        return dp[ch1.length][ch2.length];
    }
}

最長公共子串

給定兩個字符串 str1 和 str2, 輸出兩個字符串的最長公共子串。

例如 abceef 和 a2b2cee3f 的最長公共子串就是 cee。公共子串是兩個串中最長連續的相同部分。

如何分析呢? 和上面最長公共子序列的分析方式相似，要進行動態規劃匹配，並且邏輯上處理更簡單，只要當前 i,j 不匹配那麼 dp 值就爲 0，如果可以匹配那麼就變成dp[i-1][j-1] + 1

核心的狀態轉移方程爲：

dp[i][j] = dp[i-1][j-1] + 1            //text1[i]==text2[j]時
dp[i][j] = 0  //text1[i]!=text2[j]時

這裏代碼和上面很相似就不寫啦，但是有個問題有的會讓你輸出最長字符串之類，你要記得用一些變量存儲值。

不同子序列

不同子序列也會出現，並且有些難度，前面這篇不同子序列問題分析講的大家可以看看。

給定一個字符串 s 和一個字符串 t ，計算在 s 的子序列中 t 出現的個數。

字符串的一個 子序列 是指，通過刪除一些（也可以不刪除）字符且不干擾剩餘字符相對位置所組成的新字符串。（例如，"ACE" 是 "ABCDE" 的一個子序列，而 "AEC" 不是）

示例 ：

輸入：s = "rabbbit", t = "rabbit"
輸出：3
解釋：
如下圖所示, 有 3 種可以從 s 中得到 "rabbit" 的方案。
(上箭頭符號 ^ 表示選取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

分析：
這個問題其實就是上面有幾個 pat 的變形拓展，其基本思想其實是一致的，上面那題問的是有幾個 pat，固定、且很短。但這裏面 t 串的長度不固定，所以處理上就要使用數組來處理而不能直接 if else。

這題的思路肯定也是動態規劃 dp 了，dp[j]的意思就是 t 串中 [0,j-1] 長字符在 s 中能夠匹配的數量(當然這個值從前往後是動態變化的)，數組大小爲dp[t.length+1]。在遍歷 s 串的每一個元素都要和 t 串中所有元素進行對比看看是否相等，如果 s 串枚舉到的這個串和 t 串中的第 j 個相等。那麼dp[j+1]+=dp[j]。你可能會問爲啥是dp[j+1], 因爲第一個元素匹配到需要將數量 + 1，而這裏爲了避免這樣的判斷我們將dp[0]=1, 這樣 t 串的每個元素都能正常的操作。

但是有一點需要注意的就是在遍歷 s 串中第 i 個字母的時候，遍歷 t 串比較不能從左向右而必須從右向左。因爲在遍歷 s 串的第 i 個字符在枚舉 dp 數組時候要求此刻數據是相對靜止的疊加 (即同一層次不能產生影響)，而從左往右進行遇到相同字符會對後面的值產生影響。區別的話可以參考下圖這個例子：

實現的代碼爲：

class Solution {
    public int numDistinct(String s, String t) {
      char s1[]=s.toCharArray();
      char t1[]=t.toCharArray();
      int dp[]=new int[t1.length+1];
      dp[0]=1;//用來疊加

      for(int i=0;i<s1.length;i++)
      {
        for(int j=t1.length-1;j>=0;j--)
        {
          if(t1[j]==s1[i])
          {
            dp[j+1]+=dp[j];
          }
        }
      }
      return dp[t1.length];
    }
}

結語

至此，簡單的動態規劃算是分享完了。

大部分簡單動態規劃還是有套路的，你看到一些數組問題、字符串問題很有可能就暗藏動態規劃。動態規劃的套路跟遞歸有點點相似，主要是找到狀態轉移方程，有時候考慮問題不能一步想的太多 (想太多可能就把自己繞進去了)，而動態規劃就是要大家對數值上下轉換計算需要了解其中關係。

對於複雜 dp 問題或者很多套一層殼確實很難看出來，但是掌握上面的常見 dp 問題和揹包問題，就可以解決大部分動態規劃問題啦 (畢竟咱們不是搞競賽遇到的還是偏簡單或者中等難度的)。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/qfQKEsfwIH1TmSGiRg_G2w