大家好，我是bigsai，好久不見，甚是想念(天天想念)！
很久前就有小夥伴被動态規劃所折磨，确實，很多題動态規劃确實太難看出了了，甚至有的題看了題解了解起來都費勁半天。
動态規劃的範圍雖然确實是很廣很難，但是從整個動态規劃出現的頻率來看，這幾種基礎的動态規劃了解容易，學習起來壓力不大，并且出現頻率非常高。
這幾個常見的動态規劃有：連續子數組最大和，子數組的最大乘積，最長遞增子序列(LIS)，最長公共子序列(LCS)，最長公共子串，最長公共子串，不同子序列。
首發公衆号<code>bigsai</code>，謝絕未聯系轉載
首先很多人問，何為動态規劃？動态規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優化的過程。通俗一點動态規劃就是從下往上(從前向後)階梯型求解數值。
那麼動态規劃和遞歸有什麼差別和聯系？
總的來說動态規劃從前向後，遞歸從後向前，兩者政策不同，并且一般動态規劃效率高于遞歸。
不過都要考慮初始狀态，上下層資料之間的聯系。很多時候用動态規劃能解決的問題，用遞歸也能解決不過很多時候效率不高可能會用到記憶化搜尋。
不太明白?
就拿求解斐波那契額數列來說，如果直接用遞歸不優化，那麼複雜度太多會進行很多重複的計算。
但是利用記憶化你可以了解為一層緩存，将求過的值存下來下次再遇到就直接使用就可以了。
實作記憶化搜尋求斐波那契代碼為：
而動态規劃的方式你可以從前往後邏輯處理，從第三個開始每個dp都是前兩個dp之和。
當然動态規劃也能有很多空間優化，有些隻用一次的值，你可以用一些變量去替代。有些二維數組很大也可以用一維數組交替替代。當然動态規劃專題很大，有很多比如樹形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的狀态方程為：
也不難解釋，如果以前一個為截至的最大子序列和大于0，那麼就連接配接本個元素，否則本個元素就自立門戶。
實作代碼為：
ps:有小夥伴問那求可以不連續的數組最大和呢？你好好想想枚舉一下正的收入囊中，那個問題沒意義的。
給你一個整數數組 nums ，請你找出數組中乘積最大的連續子數組（該子數組中至少包含一個數字），并傳回該子數組所對應的乘積。
示例 :
輸入: [2,3,-2,4] 解釋: 子數組 [2,3] 有最大乘積 6。
連續子數組的最大乘積，這也是一道經典的動态規劃問題，但是和普通動态規劃又有點小不同。
如果資料中都是非負數，對于連續數組的最大乘積，那樣處理起來和前面連續子數組最大和處理起來有些相似，要麼和前面的疊乘，要麼自立門戶。
但是這裡面的資料會出現負數，乘以一個負數它可能從最大變成最小，并且還有負負得正就又可能變成最大了。
這時候該怎麼考慮呢？
容易，我們開兩個dp，一個<code>dpmax[]</code>記錄乘積的最大值，一個<code>dpmin[]</code>記錄乘積的最小值。然後每次都更新dpmax和dpmin不管目前值是正數還是負數.這樣通過這兩個數組就可以記錄乘積的絕對值最大。
動态方程也很容易
看一個過程就能了解明白，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才是最大的，是以暴力枚舉所有情況的時間複雜度還是非常高的。
如果我們采取動态規劃的方法，建立的<code>dp[]</code>數組，dp[i]表示以<code>nums[i]</code>結尾的最長遞增子序列，而dp[i]的求解方式就是枚舉i号前面的元素和對應結尾的最長子序列，找到一個元素值小于<code>nums[i]</code>并且遞增序列最長，這樣的時間複雜度為O(n2)。
狀态轉移方程為：
具體流程為：
不過這道題還有一個優化，可以優化成O(nlogn)的時間複雜度。
我們用dp記錄以 <code>nums[i]</code> 結尾的最長子序列長度,縱觀全局，我們希望在長度一緻的情況下末尾的值能夠盡量的小！
例如 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做鋪墊。
而這個思路的核心就是維護一個<code>lenth[]</code>數組，length[i]表示長度為i的子序列末尾最小值，因為我們每次順序增加一個長度說明這個值比前面的都大(做了充分比較)，是以這個數組也是個遞增的，遞增，那麼在鎖定位置更新最大長度序列尾值的時候可以使用二分法優化。
最長公共子序列也成為LCS.出現頻率非常高！
給定兩個字元串 text1 和 text2，傳回這兩個字元串的最長 公共子序列 的長度。如果不存在 公共子序列 ，傳回 0 。
一個字元串的 子序列 是指這樣一個新的字元串：它是由原字元串在不改變字元的相對順序的情況下删除某些字元（也可以不删除任何字元）後組成的新字元串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
兩個字元串的 公共子序列 是這兩個字元串所共同擁有的子序列。
拿b c d d e和 a c e e d e舉例，其的公共子串為c d e。如果使用暴力，複雜度太高會直接逾時，就需要使用動态規劃。兩個字元串比對，我們設立二維<code>dp[][]</code>數組，<code>dp[i][j]</code>表示text1串第i個結尾，text2串第j個結尾的最長公共子串的長度。
這裡核心就是要搞懂狀态轉移，分析<code>dp[i][j]</code>的轉換情況，當到達i,j時候：
如果<code>text1[i]==text2[j]</code>,因為兩個元素都在最末尾的位置，是以一定可以比對成功，換句話說，這個位置的鄰居dp值不可能大于他（最多相等）。是以這個時候就是<code>dp[i][j]</code>=<code>dp[i-1][j-1]</code> +<code>1</code>;
如果<code>text1[i]!=text2[j]</code>，就有兩種可能性，我們知道的鄰居有<code>dp[i-1][j]</code>,<code>dp[i][j-1]</code>，很多人還會想到<code>dp[i-1][j-1]</code>這個一定比前兩個小于等于，因為就是前面兩個子範圍嘛！是以這時就相當于末尾比對不成，就要看看鄰居能比對的最大值啦，此時<code>dp[i][j]</code>=<code>max(dp[i][j-1],dp[i-1][j])</code>。
是以整個狀态轉移方程為：
給定兩個字元串str1和str2,輸出兩個字元串的最長公共子串。
例如 abceef 和a2b2cee3f的最長公共子串就是cee。公共子串是兩個串中最長連續的相同部分。
如何分析呢? 和上面最長公共子序列的分析方式相似，要進行動态規劃比對，并且邏輯上處理更簡單，隻要目前i,j不比對那麼dp值就為0，如果可以比對那麼就變成<code>dp[i-1][j-1] + 1</code>
核心的狀态轉移方程為：
這裡代碼和上面很相似就不寫啦，但是有個問題有的會讓你輸出最長字元串之類，你要記得用一些變量存儲值。
不同子序列也會出現，并且有些難度，前面這篇不同子序列問題分析講的大家可以看看。
給定一個字元串 s 和一個字元串 t ，計算在 s 的子序列中 t 出現的個數。
字元串的一個 子序列 是指，通過删除一些（也可以不删除）字元且不幹擾剩餘字元相對位置所組成的新字元串。（例如，"ACE" 是 "ABCDE" 的一個子序列，而 "AEC" 不是）
示例 ：
分析：
這個問題其實就是上面有幾個pat的變形拓展，其基本思想其實是一緻的，上面那題問的是有幾個pat，固定、且很短。但這裡面t串的長度不固定，是以處理上就要使用數組來處理而不能直接if else。
這題的思路肯定也是動态規劃dp了，<code>dp[j]</code>的意思就是t串中[0,j-1]長字元在s中能夠比對的數量(當然這個值從前往後是動态變化的)，數組大小為<code>dp[t.length+1]</code>。在周遊s串的每一個元素都要和t串中所有元素進行對比看看是否相等，如果s串枚舉到的這個串和t串中的第j個相等。那麼<code>dp[j+1]+=dp[j]</code>。 你可能會問為啥是<code>dp[j+1]</code>,因為第一個元素比對到需要将數量+1，而這裡為了避免這樣的判斷我們将<code>dp[0]=1</code>,這樣t串的每個元素都能正常的操作。
但是有一點需要注意的就是在周遊s串中第i個字母的時候，周遊t串比較不能從左向右而必須從右向左。因為在周遊s串的第i個字元在枚舉dp數組時候要求此刻資料是相對靜止的疊加(即同一層次不能産生影響)，而從左往右進行遇到相同字元會對後面的值産生影響。差別的話可以參考下圖這個例子：
實作的代碼為：
至此，簡單的動态規劃算是分享完了。
大部分簡單動态規劃還是有套路的，你看到一些數組問題、字元串問題很有可能就暗藏動态規劃。動态規劃的套路跟遞歸有點點相似，主要是找到狀态轉移方程，有時候考慮問題不能一步想的太多(想太多可能就把自己繞進去了)，而動态規劃就是要大家對數值上下轉換計算需要了解其中關系。
對于複雜dp問題或者很多套一層殼确實很難看出來，但是掌握上面的常見dp問題和背包問題，就可以解決大部分動态規劃問題啦(畢竟咱們不是搞競賽遇到的還是偏簡單或者中等難度的)。
原創不易，求個三連！