No.1
最簡單的動態(tài)規(guī)劃題目
侄女5歲現(xiàn)在開始學習加減法了，每次做數(shù)學都離不開她的小手指，超過5的就開始數(shù)另一個手的手指，真是汗顏啊
有一天，我問她
“1+1+1+1+1等于多少？”
“搬起小拇指，就開始數(shù)了，5！”
“那么再加一個1呢？”
“當然是6了” -脫口而出
“這次你怎么算這么快的？”
“剛剛不是5嗎，加1就是6了啊”
“所以你不需要重新計算，因為你記得之前的答案是5！動態(tài)規(guī)劃就是說：記住之前的東西可以節(jié)省時間”
玩歸玩，鬧歸鬧，別拿dp開玩笑！\color{red}{玩歸玩，鬧歸鬧，別拿dp開玩笑！}玩歸玩，鬧歸鬧，別拿dp開玩笑！
來瞅一眼科普中國科學百科的詞條解釋
動態(tài)規(guī)劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優(yōu)化的過程。20世紀50年代初，美國數(shù)學家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動態(tài)規(guī)劃。動態(tài)規(guī)劃的應用極其廣泛，包括工程技術、經(jīng)濟、工業(yè)生產(chǎn)、軍事以及自動化控制等領域，并在背包問題、生產(chǎn)經(jīng)營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統(tǒng)可靠性問題等中取得了顯著的效果。
看不完的童鞋跳過，咱整點簡單點的
其實剛剛這道題應該算是最簡單的動態(tài)規(guī)劃題目了。
我們可以看出這道題有什么特點呢？
我們知道之所以最后一步加1會計算的那么快，大部分要歸功于之前計算過答案是5，如果我們把問題歸納為一個子問題，我想要計算每一步的答案，就可以列出一個方程：f(x) = f(x -1) + 1, 大家別對f(x)發(fā)怵，就把它當做一個簡單的方法。
其中，f(x)為第幾步的值，設定一個初始值，x > 0, 則第一步
f(1) = 1;
f(2) = f(1) + 1;
...
f(6) = f(5) + 1
在程序的世界里，用什么東東來存一個可以記錄之前結果值的數(shù)據(jù)結構呢？
顯而易見：數(shù)組唄。直接利用下標來存，巴適, 這就是動態(tài)規(guī)劃里的動態(tài)，規(guī)劃就是限定一些邊界和初始化。
看到這里，老鐵，你就會動態(tài)規(guī)劃了，來看第二題。
No.2
leecode 322: 你有三種硬幣，2元、5元、7元，每種硬幣足夠多，買一本書需要27元，用最少的硬幣組合
怎么感覺像是回到了小學應用題？
--簡單分析一下： 最小硬幣組合 -> 盡量用大的硬幣
這傻不拉幾的題誰出的，這么簡單
7+7+7=21,21+2+2+2=27， 6枚硬幣
臥槽
7+5+5+5+5=27， 5枚硬幣
我們可以很暴力的想一想，從大往小的算，可以加起來不超過27，比如
7+7+7+7 > 27 (排除）
7+7+7+5 或者 7 +7 +7+2+2+2 6枚
....
窮舉太慢了，還會涉及到很多的重復計算，如果我想要27以內的任何值最小的硬幣組合呢，想想都頭大了吧。
既然計算機可以通過內存保存之前的內容，又快，很明顯，我們開一個數(shù)組來保存之前的狀態(tài)。
重點預警
1.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
簡單的說，解動態(tài)規(guī)劃的時候需要開一個數(shù)組，數(shù)組的每個元素f[i]或者f[i][j]代表什么，類似數(shù)學題中x, y, z代表什么
解動態(tài)規(guī)劃需要兩個意識：
最后一步
子問題
最后一步
剛剛第一題不是說了嘛，最后一步的計算結果是5。對于這道題，雖然我們不知道最優(yōu)策略是什么，但是最優(yōu)策略肯定是K枚硬幣，a1, a2, ....ak面值加起來是27
所以一定有一枚最后的硬幣:ak.
除掉這么硬幣，前面硬幣的面值加起來是27-ak
關鍵點1：
我們不關心前面的k-1枚硬幣是怎么拼出27-ak的（可能有一種拼法，也可能有100種拼法），而且我們現(xiàn)在甚至還不知道ak和K, 但是我們確定前面的硬幣拼出了27-ak
關鍵點2：
因為是最優(yōu)策略， 所以拼出27-ak的硬幣數(shù)一定要最少，否則這就不是最優(yōu)策略了
子問題
所以我們就要求：最少用多少枚硬幣可以拼出27-ak
原問題是最少用多少枚硬幣拼出27
我們將原問題轉化了一個子問題，而且規(guī)模更?。?7-ak
為了簡化定義， 我們設狀態(tài)f(x）=最少用多少枚硬幣拼出x
等等，我們還不知道最后的那枚硬幣ak是多少
很明顯，最后的那枚硬幣只能是2,5或者7
如果ak是2， f(27)應該是f(27-2)+1(1代表最后一枚硬幣2）
如果ak是5， f(27)應該是f(27-5)+1(1代表最后一枚硬幣5）
如果ak是7， f(27)應該是f(27-7)+1(1代表最后一枚硬幣7）
所以使用最少的硬幣數(shù)=f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}
1.2. 動態(tài)規(guī)劃組成部分2：轉移方程
設狀態(tài)f(x)=最少用多少枚硬幣拼出x
對于任意的x : f(X) = min{f(X-2)+1, f(X-5)+1, f(X-7)+1}
1.3. 動態(tài)規(guī)劃組成部分2：初始條件和邊界情況
提出問題
x-2, x-5, x-7 小于0怎么辦？
什么時候停下來？
1.3.1
如果不能拼出Y, 就定義f[Y] = 正無窮
例如f[-1], f[-2] = 正無窮
例如：拼不出f[1]=min{f(-1)+1, f(-3)+1, f(-6)+1}
初始條件：f[0] = 0
2.4. 動態(tài)規(guī)劃組成部分2：計算順序
計算：f[1], f[2], ... f[27]
當我們計算到f[x], f[x-2], f[x-5], f[x-7] 都已經(jīng)得到結果了
如圖：
f[x] = 最少用多少枚硬幣拼出x
f[x] = ∞ 表示無法用硬幣拼出x
參考代碼
publicstaticintcoinChange(int[] A,intM ){int[] f =newint[M+1];intn = A.length; f[0] =0;inti,j;for(i =1; i<=M; i++) {? ? f[i] = Integer.MAX_VALUE;for(j =0; j< n;j++) {// 邊界條件判斷if(i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {? ? ? ? ? ? f[i] = Math.min(f[i - A[j]] +1, f[i]);//? System.out.println(i + "=" +f[i]);}? ? } }if(f[M] == Integer.MAX_VALUE) {? ? f[M] = -1; }returnf[M];}@TestpublicvoidisCoinChange(){intxx = {1,2,3};intb =6;inti = coinChange(xx, b);? ? Assert.assertNotNull(i);}復制代碼
??
核心代碼就4行，是不是很簡單?\color{red}{核心代碼就4行，是不是很簡單~}核心代碼就4行，是不是很簡單?
No.3
leecode 62 ：不同路徑
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為 “Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為 “Finish” ）。
問總共有多少條不同的路徑？
看了上面的解題步驟，按部就班的來
2.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
最后一步
無論機器人用何種方式到達右下角，總有最后挪動的一步：-向右或者向下
如果所示，我們設右下角的坐標為(m-1,n-1)
那么最后一步的前一步機器人的位置在（m-2,n-1)或者(m-1,n-2)
子問題
那么，如果機器人有x種方式從左上角走到(m-2,n-1), 有Y種方式從左上角走到(m-1,n-2), 則機器人有X+Y的方式走到(m-1,n-1)
問題轉化為，機器人有多少種 方式從左上角走到(m-2,n-1)或者(m-1,m-2）
如果走到是(m-2,n-1)如圖：
我們可以直接干掉最后一列
同理如果是走到(m-1,n-2)行就減少一行。
狀態(tài)：
設f[i][j]為機器人有多少種方式從左上角走到(i,j)
2.2. 動態(tài)規(guī)劃組成部分2：轉移方程
對于任意一個格子：
f[i][j] = f[i-1][j] + f[i][j-1]
1? ? ? 2? ? ? 3
1代表機器人有多少種方式走到[i][j]
2代表機器人有多少種方式走到f[i-1][j]
3代表機器人有多少種方式走到f[i][j-1]
2.3. 動態(tài)規(guī)劃組成部分3：初始條件和邊界情況
初始條件：f[0][0]=1,因為機器人只有一個方式到左上角
邊界情況：i=0或j=0，則前一步只能有一個方向過來，也就是說第0行或者第0列，每走一步只有一種情況，則f[i][j] = 1,其他區(qū)域都滿足轉移方程。
3.4. 動態(tài)規(guī)劃組成部分4：計算順序
按行計算，為什么按行計算呢？
對于這道題來說，按行計算在計算到f[1][1]時，f[0][1]和f[1][0]都已經(jīng)計算了，同樣按列計算這兩坐標也計算了，不用再次計算。
f[0][0] =? 1
計算第0行：f[0][0],f[0][1],...,f[0][n-1]
計算第1行：f[1][0],f[1][1],...,f[1][n-1]
...
計算第m-1行：f[m-1][0],f[m-1][1],...,f[m-1][n-1]
時間復雜度：O(mn)
參考代碼
publicintuniquePaths(intm,intn){int[][] f =newint[m][n];inti,j;for(i =0; i
能看到這里的朋友，你已經(jīng)超過80%的人，可能現(xiàn)在你的腦袋開始有點暈了，刷題就是這樣，刷幾道就會頭疼，休息下就好了，這玩兒意兒看得就是堅持.
總結一下
什么題可以選擇動態(tài)規(guī)劃來做？
1.計數(shù)
有多少種方式走到右下角
有多少種方法選出k個數(shù)是的和是sum
2.求最大值最小值
從左上角走到右下角路徑的最大數(shù)字和
最長上升子序列長度
3.求存在性
取石子游戲,先手是否必勝
能不能選出k個數(shù)使得和是sum
好叻！接下來咱們整第四道題。
No.4
leecode 5. 最長回文子串
給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1：輸入: "babad"
輸出: "bab" 注意: "aba" 也是一個有效答案。
示例 2：輸入: "cbbd"
輸出: "bb"
看了之前的文章，我們就四步走吧
1.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
簡單的說，解動態(tài)規(guī)劃的時候需要開一個數(shù)組，數(shù)組的每個元素f[i]或者f[i][j]代表什么，類似數(shù)學題中x, y, z代表什么
在這道題中，我們定義f[i][j] 表示字符串 s 的第 i 到 j 個字母組成的串是否為回文串
解動態(tài)規(guī)劃需要兩個意識：
最后一步
子問題
最后一步
我們用示例一來講解，下圖是第一步和第二步的判斷過程，很明顯最后一步為下標為4的字母b與前面所有元素進行比較，得出最長的回文子串。
子問題
我們可以看到如果f[i] =f[j]，要判定它是一個回文串，需要判定
f[i]j] = f[i+1]f[j-1] ： 從i到j是一個回文串，那么從i+1到j-1一定也是一個回文串
也就是如上圖需要判定a=a
1.2. 動態(tài)規(guī)劃組成部分2：轉移方程
對于從i到j長度的字符串，判定它是一個回文串：
f[i]j] = f[i+1]f[j-1]
同時我們也知道，f[i+1][j-1]這是一個已知的，因為最后一步的上一步已經(jīng)將結果保存,也就是f[i+1][j-1] = f[i+2]f[j-2]
1.3. 動態(tài)規(guī)劃組成部分3：初始條件和邊界情況
當剩余判定字母個數(shù)<3 并且 f[i] = f[j]，它一定是回文串。
對于字母本身來說f[i][i],從i到i的字符串，它也是回文。
1.4. 動態(tài)規(guī)劃組成部分4：計算順序
如上圖，我們用j去匹配0~i (i < j)
它的時間復雜度是On^2,由于是二維數(shù)據(jù)空間復雜度也是On^2
當然也有其他的解決辦法如中心擴散和馬拉車。
參考代碼
// 動態(tài)規(guī)劃publicStringlongestPalindrome(String s){// 特判intlen = s.length();if(len <2) {returns;? ? }intmaxLen =1;intbegin =0;// dp[i][j] 表示 s[i, j] 是否是回文串boolean[][] dp =newboolean[len][len];char[] charArray = s.toCharArray();for(inti =0; i < len; i++) {? ? ? ? dp[i][i] =true;// 對本身來說就是回文}for(intj =1; j < len; j++) {for(inti =0; i < j; i++) {if(charArray[i] != charArray[j]) {? ? ? ? ? ? ? ? dp[i][j] =false;? ? ? ? ? ? }else{if(j - i <3) {? ? ? ? ? ? ? ? ? ? dp[i][j] =true;? ? ? ? ? ? ? ? }else{? ? ? ? ? ? ? ? ? ? dp[i][j] = dp[i +1][j -1];// 要滿足這個條件，必需先滿足j - i > 3考慮邊界}? ? ? ? ? ? }// 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此時記錄回文長度和起始位置if(dp[i][j] && j - i +1> maxLen) {? ? ? ? ? ? ? ? maxLen = j - i +1;? ? ? ? ? ? ? ? begin = i;? ? ? ? ? ? }? ? ? ? }? ? }returns.substring(begin, begin + maxLen);}@TestpublicvoidislongestPalindrome(){? ? String i = longestPalindrome("babaxaxab");? ? Assert.assertNotNull(i);}復制代碼
準備來一道非常實用的題目?? ?? ??
No.5
leecode 10. 正則表達式匹配
給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 '.' 和 '*' 的正則表達式匹配。
'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋 整個 字符串 s的，而不是部分字符串。
示例 1：
輸入：s = "aab" p = "cab"
輸出：true
解釋：因為 '*' 表示零個或多個，這里 'c' 為 0 個, 'a' 被重復一次。因此可以匹配字符串 "aab"。
示例 2：
輸入：s = "mississippi" p = "misisp*."
輸出：false
解釋：第二個*不能匹配si
2.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
wc，你倒是說說怎么確定要用動態(tài)規(guī)劃來做啊？
看題目，需要逐步匹配
沒有時間復雜度空間復雜度限制，你可以選擇>On的
跟前面題很類似，這里需要考慮* 和 .的情況。
嘗試根據(jù)步驟寫出轉移方程
在這道題中，我們定義f[i][j] 表示字符串 s 的前 i 個字符與 字符串p的前 j 個字符是否匹配
解動態(tài)規(guī)劃需要兩個意識：
最后一步
子問題
最后一步
我們用示例來講解 ：s = "aaab" p = "aa*b"
根據(jù)題目意思，我們知道s要被全匹配，我們直接用s去匹配p字符串的每一個字符，這樣我們的最后一步就是用s字符串中的b字符去匹配p字符串的每一個字符，匹配最后一個字符為b是否相等。
子問題
有幾種情況需要討論，也就是用s去匹配p最后一個匹配的字符j
如果都是字符，只需要判斷：f[i][j] = f[i-1][j-1]
如果是“.” ,說明可以匹配s的最后任意一個字符，也只需：
f[i][j] = f[i-1][j-1]
如果是“*”，分兩種情況一種是匹配零個字符，一種是匹配1個或多個字符
如果是匹配零個字符：f[i][j] = f[i][j-2] ，因為如果j是*，我們就可以對p的j-1匹配任意次數(shù)，當然零次就是j-2了。
? ? 如果是匹配1個或多個字符：f[i][j] = f[i-1][j]，匹配 s 末尾的一個字符，將該字符扔掉，而該組合還可以繼續(xù)進行匹配,簡單點說，零個我們判定了，如果是一個我們扔掉一個字符，如果能匹配則保存，如果匹配兩個，我們是知道匹配s的上一個字符的結果的，直接匹配就行，同樣匹配多個也是如此。（匹配多個是根據(jù)前一個的匹配結果得出來的）
2.2. 動態(tài)規(guī)劃組成部分2：轉移方程
在子問題中我們分析的幾種情況就是轉移方程
2.3. 動態(tài)規(guī)劃組成部分3：初始條件和邊界情況
因為要涉及到i-1和j-1，注意邊界
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0]=true
2.4. 動態(tài)規(guī)劃組成部分4：計算順序
用s去匹配p字符串的每一個字符
它的時間復雜度是Onm,由于是二維數(shù)據(jù)空間復雜度是Onm
參考代碼
publicbooleanisMatch(String s, String p){intm = s.length();intn = p.length();boolean[][] f =newboolean[m +1][n +1];? ? f[0][0] =true;for(inti =0; i <= m; ++i) {for(intj =1; j <= n; ++j) {if(p.charAt(j -1) =='*') {? ? ? ? ? ? ? ? f[i][j] = f[i][j -2];if(matches(s, p, i, j -1)) {? ? ? ? ? ? ? ? ? ? f[i][j] = f[i][j] || f[i -1][j];? ? ? ? ? ? ? ? }? ? ? ? ? ? }else{if(matches(s, p, i, j)) {? ? ? ? ? ? ? ? ? ? f[i][j] = f[i -1][j -1];? ? ? ? ? ? ? ? }? ? ? ? ? ? }? ? ? ? }? ? }returnf[m][n];}publicbooleanmatches(String s, String p,inti,intj){if(i ==0) {returnfalse;? ? }if(p.charAt(j -1) =='.') {returntrue;? ? }returns.charAt(i -1) == p.charAt(j -1);}@TestpublicvoidisisMatch(){booleani = isMatch("aa","a*");? ? Assert.assertNotNull(i);}復制代碼
No.6
繼續(xù)干，繼續(xù)干????????
leecode 32. 最長有效括號
給你一個只包含 '(' 和 ')' 的字符串，找出最長有效（格式正確且連續(xù)）括號子串的長度。
示例 1：
輸入：s = "(()"
輸出：2
解釋：最長有效括號子串是 "()"
示例 2：
輸入：s = ")()())"
輸出：4
解釋：最長有效括號子串是 "()()"
示例 3：
輸入：s = ""
輸出：0
提示：
0 <= s.length <= 3 * 104
s[i] 為 '(' 或 ')'
看了之前的文章，我們就四步走吧
1.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
簡單的說，解動態(tài)規(guī)劃的時候需要開一個數(shù)組，數(shù)組的每個元素f[i]或者f[i][j]代表什么，類似數(shù)學題中x, y, z代表什么
wc，你倒是說說怎么確定要用動態(tài)規(guī)劃來做?。?/p>
看題目，需要逐步驗證最長長度
沒有時間復雜度空間復雜度限制，你可以選擇>=On的
跟前面題很類似，這里需要考慮生成括號的情況。
嘗試根據(jù)步驟寫出轉移方程
在這道題中，我們定義d[i]表示以下標 ii字符結尾的最長有效括號的長度
解動態(tài)規(guī)劃需要兩個意識：
最后一步
子問題
最后一步
我們用下圖來講解，i作為最后一個括號判斷，我們只對為左括號做判斷，左括號分兩種情況，具體看子問題拆分。
子問題
第一種情況為： ...()
因為括號前面可能還有有效的括號，之前我們定義了d[i] 表示下標i字符結尾的最長有效括號的長度，所以可以推導出：
d[i] = d[i-2] + 2
第二種情況為： ...))
>need-to-insert-img
如圖，下標為2：i - d[i-1] -1
提出一個疑問：在下標2和5之前可能存在多個有效括號，其實都是d[i-1],因為我們定義的：d[i-1] 表示下標i-1字符結尾的最長有效括號的長度
>need-to-insert-img
最長有效括號的長度 ：
d[i] = x + y
這里x = d[i - d[i-1] -2]
這里y = d[i-1] + 2
因此 ：d[i] = d[i - d[i-1] -2] + d[i-1] + 2
1.2. 動態(tài)規(guī)劃組成部分2：轉移方程
d[i] 表示下標i字符結尾的最長有效括號的長度
d[i] = d[i - d[i-1] -2] + d[i-1] + 2
1.3. 動態(tài)規(guī)劃組成部分3：初始條件和邊界情況
跟之前有些題一樣，我們需要判斷第i字符去判斷第i-1個字符，所以i從1開始遍歷，判斷數(shù)組i-2需要考慮越界。
① ...()? : i >=2
② ...))? :? i - d[i-1] > 0? 對應 ：())
1.4. 動態(tài)規(guī)劃組成部分4：計算順序
從左往右
它的時間復雜度是On,空間復雜度也是On
當然也有其他的解決辦法如棧
參考代碼
public int longestValidParentheses(String s) {? ? int maxans = 0;? ? int[] dp = new int[s.length()];? ? for (int i = 1; i < s.length(); i++) {? ? ? ? if (s.charAt(i) == ')') {? ? ? ? ? ? if (s.charAt(i - 1) == '(') {? ? ? ? ? ? ? ? dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;? ? ? ? ? ? } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {? ? ? ? ? ? ? ? dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;? ? ? ? ? ? }? ? ? ? ? ? maxans = Math.max(maxans, dp[i]);? ? ? ? }? ? }? ? return maxans;}@Testpublic void isLongestValidParentheses() {? ? String s = "()(())";? ? longestValidParentheses(s);}復制代碼
No.7
這道題相對于就簡單一些啦---來自禿頂?shù)墓こ處??????????
leecode 42. 接雨水
給定 n 個非負整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。
>need-to-insert-img
輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。
示例 2：
輸入：height = [4,2,0,3,2,5]
輸出：9
提示：
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
看了之前的文章，我們就四步走吧
這道題相對而言，提升了難度，常規(guī)的題，我們的計算順序一般是從左到右，或者從右到左，亦或是從上到下。
1.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
簡單的說，解動態(tài)規(guī)劃的時候需要開一個數(shù)組，數(shù)組的每個元素f[i]或者f[i][j]代表什么，類似數(shù)學題中x, y, z代表什么
wc，你倒是說說怎么確定要用動態(tài)規(guī)劃來做?。?/p>
看題目，需要逐步驗證最長長度
沒有時間復雜度空間復雜度限制，你可以選擇>=On的
跟前面題很類似，這里需要考慮每一步最高的高度取低位高度，因為可能形成低洼
嘗試根據(jù)步驟寫出轉移方程
在這道題中，我們定義d[i]表示以下標 i字符結尾的最多的有效雨水
解動態(tài)規(guī)劃需要兩個意識：
最后一步
子問題
最后一步
我們可以利用填滿法來降低復雜度。去掉低洼的情況。
先從左到右來看，求出每個位置的最大高度（深度）
>need-to-insert-img
從右往左看，求出每個位置的最大高度
>need-to-insert-img
我們在來看它們重疊之后的效果
>need-to-insert-img
這樣每個位置的最小值 - 高度就是每個位置的蓄水值。
子問題
我們存儲了從左到右和從右到左每個位置的最大值
從重疊的圖中可以看到最后一個位置的最小值為2，減去高度，蓄水值為0.
1.2. 動態(tài)規(guī)劃組成部分2：轉移方程
ans += Math.min(left_max[i], right_max[i]) - height[i];
1.3. 動態(tài)規(guī)劃組成部分3：初始條件和邊界情況
1.4. 動態(tài)規(guī)劃組成部分4：計算順序
從左到右 + 從右到左
它的時間復雜度是On,空間復雜度也是On
當然也有其他的解決辦法如棧
參考代碼
publicinttrap(int[] height){if(height ==null|| height.length ==0)return0;intans =0;intsize = height.length;int[] left_max =newint[size];int[] right_max =newint[size];? ? left_max[0] = height[0];for(inti =1; i < size; i++) {? ? ? ? left_max[i] = Math.max(height[i], left_max[i -1]);? ? }? ? right_max[size -1] = height[size -1];for(inti = size -2; i >=0; i--) {? ? ? ? right_max[i] = Math.max(height[i], right_max[i +1]);? ? }for(inti =1; i < size -1; i++) {? ? ? ? ans += Math.min(left_max[i], right_max[i]) - height[i];? ? }returnans;}@Testpublicvoidistrap(){int[] candidates = {2,0,6,1};inti = trap(candidates);? ? Assert.assertNotNull(i);}復制代碼
No.8
這道題跟第五題很類似，如果看懂了第五題，那么這題肯定是信手拈來????????
leecode 44. 通配符匹配
給定一個字符串 (s) 和一個字符模式 (p) ，實現(xiàn)一個支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何單個字符。
'*' 可以匹配任意字符串（包括空字符串）。
兩個字符串完全匹配才算匹配成功。
說明:
s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 ? 和 *。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串。
示例 2:
輸入:
s = "aa"
p = "*"
輸出: true
解釋: '*' 可以匹配任意字符串。
示例 3:
輸入:
s = "cb"
p = "?a"
輸出: false
解釋: '?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b'。
示例 4:
輸入:
s = "adceb"
p = "ab"
輸出: true
解釋: 第一個 '' 可以匹配空字符串, 第二個 '' 可以匹配字符串 "dce".
示例 5:
輸入:
s = "acdcb"
p = "a*c?b"
輸出: false
看了之前的文章，我們就四步走吧
1.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
簡單的說，解動態(tài)規(guī)劃的時候需要開一個數(shù)組，數(shù)組的每個元素f[i]或者f[i][j]代表什么，類似數(shù)學題中x, y, z代表什么
wc，你倒是說說怎么確定要用動態(tài)規(guī)劃來做啊？
看題目，需要逐步驗證最長長度
沒有時間復雜度空間復雜度限制，你可以選擇>=On的
跟前面題很類似，這里需要考慮* 和 ？的情況。
嘗試根據(jù)步驟寫出轉移方程
在這道題中，我們定義f[i][j] 表示字符串 s 的前 i 個字符與 字符串p的前 j 個字符是否匹配
解動態(tài)規(guī)劃需要兩個意識：
最后一步
子問題
最后一步
我們用示例來講解 ：s = "aaab" p = "aa*b"
根據(jù)題目意思，我們知道s和p要全匹配，我們直接用s去匹配p字符串的每一個字符，這樣我們的最后一步就是用s字符串中的b字符去匹配p字符串的每一個字符，匹配最后一個字符為b是否相等。
子問題
這是 '動態(tài)規(guī)劃Day two - 正則表達式匹配' 的子問題分析
有幾種情況需要討論，也就是用s去匹配p最后一個匹配的字符j
如果都是字符，只需要判斷：f[i][j] = f[i-1][j-1]
如果是“.” ,說明可以匹配s的最后任意一個字符，也只需：
f[i][j] = f[i-1][j-1]
如果是“*”，分兩種情況一種是匹配零個字符，一種是匹配1個或多個字符
如果是匹配零個字符：f[i][j] = f[i][j-2] ，因為如果j是*，我們就可以對p的j-1匹配任意次數(shù)，當然零次就是j-2了。
如果是匹配1個或多個字符：f[i][j] = f[i-1][j]，匹配 s 末尾的一個字符，將該字符扔掉，而該組合還可以繼續(xù)進行匹配,簡單點說，零個我們判定了，如果是一個我們扔掉一個字符，如果能匹配則保存，如果匹配兩個，我們是知道匹配s的上一個字符的結果的，直接匹配就行，同樣匹配多個也是如此。（匹配多個是根據(jù)前一個的匹配結果得出來的）
這道題基本上是如出一轍
有幾種情況需要討論，也就是用s去匹配p最后一個匹配的字符j
如果都是字符，只需要判斷：f[i][j] = f[i-1][j-1]
如果是“？” ,說明可以匹配s的最后任意一個字符，也只需：
f[i][j] = f[i-1][j-1]
如果是“”，分兩種情況，第一種是不需要使用,第二種是需要使用*
實例 ：s = "abc"? p = "a*"。
在對s串的a遍歷p串的*時，剛好滿足dp[i][j] = dp[i][j-1] 此時i=1,j=2,
dp[1][2] = dp[1][1]=true。? ---不需要使用*
在對s串的b遍歷p串的時，剛好滿足dp[i][j] = f[i-1][j],因為是可以匹配任意一個字母的。
dp[2][2] = dp[1][2]=true。---需要使用*
在對s串的c遍歷p串的時，剛好滿足dp[i][j] = f[i-1][j],因為是可以匹配任意一個字母的。
dp[3][2] = dp[2][2]=true。---不需要使用*
1.2. 動態(tài)規(guī)劃組成部分2：轉移方程
轉移方程可以詳見子問題分析
1.3. 動態(tài)規(guī)劃組成部分3：初始條件和邊界情況
因為要涉及到i-1和j-1，注意邊界
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0]=true
當f[0][j]時，需要判斷j是否為*，因為*可以匹配null串
1.4. 動態(tài)規(guī)劃組成部分4：計算順序
用s串的每一個字符去匹配p串的每一個字符
它的時間復雜度是Onm,空間復雜度也是Onm
參考代碼
publicbooleanisWildcardMatch(String s, String p){intm = s.length();intn = p.length();boolean[][] dp =newboolean[m +1][n +1];? ? dp[0][0] =true;for(inti =1; i <= n; ++i) {if(p.charAt(i -1) =='*') {? ? ? ? ? ? dp[0][i] =true;? ? ? ? }else{break;? ? ? ? }? ? }for(inti =1; i <= m; ++i) {for(intj =1; j <= n; ++j) {if(p.charAt(j -1) =='*') {? ? ? ? ? ? ? ? dp[i][j] = dp[i][j -1] || dp[i -1][j];? ? ? ? ? ? }elseif(p.charAt(j -1) =='?'|| s.charAt(i -1) == p.charAt(j -1)) {? ? ? ? ? ? ? ? dp[i][j] = dp[i -1][j -1];? ? ? ? ? ? }? ? ? ? }? ? }returndp[m][n];}@TestpublicvoidisisWildcardMatch(){booleani = isWildcardMatch("123","1*");? ? Assert.assertNotNull(i);}復制代碼
No.9
這道題就很簡單了，放松一下~????????
63. 不同路徑 II
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為“Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為“Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？
>need-to-insert-img
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。
示例 1：
>need-to-insert-img
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：
3x3 網(wǎng)格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
\1. 向右 -> 向右 -> 向下 -> 向下
\2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
>need-to-insert-img
輸入：obstacleGrid = [[0,1],[0,0]]
輸出：1
提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 為 0 或 1
本題與
---
---
里的不同路徑1，大致相同，只是增加了障礙物，我們做一下沒有障礙物的判斷就行了。
2.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
最后一步
無論機器人用何種方式到達右下角，總有最后挪動的一步：-向右或者向下
如果所示，我們設右下角的坐標為(m-1,n-1)
那么最后一步的前一步機器人的位置在（m-2,n-1)或者(m-1,n-2)
子問題
那么，如果機器人有x種方式從左上角走到(m-2,n-1), 有Y種方式從左上角走到(m-1,n-2), 則機器人有X+Y的方式走到(m-1,n-1)
問題轉化為，機器人有多少種 方式從左上角走到(m-2,n-1)或者(m-1,m-2）
如果走到是(m-2,n-1)如圖：
>need-to-insert-img
我們可以直接干掉最后一列
同理如果是走到(m-1,n-2)行就減少一行。
狀態(tài)：
設f[i][j]為機器人有多少種方式從左上角走到(i,j)
2.2. 動態(tài)規(guī)劃組成部分2：轉移方程
對于任意一個格子：
f[i][j] = f[i-1][j] + f[i][j-1]
1? ? ? ? ? 2? ? ? ? ? ? 3
1代表機器人有多少種方式走到[i][j]
2代表機器人有多少種方式走到f[i-1][j]
3代表機器人有多少種方式走到f[i][j-1]
2.3. 動態(tài)規(guī)劃組成部分3：初始條件和邊界情況
初始條件：f[0][0]=1,因為機器人只有一個方式到左上角
邊界情況：i=0或j=0，則前一步只能有一個方向過來，也就是說第0行或者第0列，每走一步只有一種情況，則f[i][j] = 1,其他區(qū)域都滿足轉移方程。
如果遇到障礙物，f[i][j] = 0。
3.4. 動態(tài)規(guī)劃組成部分4：計算順序
按行計算，為什么按行計算呢？
對于這道題來說，按行計算在計算到f[1][1]時，f[0][1]和f[1][0]都已經(jīng)計算了，同樣按列計算這兩坐標也計算了，不用再次計算。
f[0][0] =? 1 如果第一個是障礙物f[0][0]=0
計算第0行：f[0][0],f[0][1],...,f[0][n-1]
計算第1行：f[1][0],f[1][1],...,f[1][n-1]
...
計算第m-1行：f[m-1][0],f[m-1][1],...,f[m-1][n-1]
時間復雜度：O(mn)
>need-to-insert-img
參考代碼
classSolution{publicintuniquePathsWithObstacles(int[][] obstacleGrid){if(obstacleGrid ==null|| obstacleGrid.length ==0) {return0;? ? }// 定義 dp 數(shù)組并初始化第 1 行和第 1 列。intm = obstacleGrid.length, n = obstacleGrid[0].length;int[][] dp =newint[m][n];for(inti =0; i < m && obstacleGrid[i][0] ==0; i++) {? ? ? ? dp[i][0] =1;? ? }for(intj =0; j < n && obstacleGrid[0][j] ==0; j++) {? ? ? ? dp[0][j] =1;? ? }// 根據(jù)狀態(tài)轉移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 進行遞推。for(inti =1; i < m; i++) {for(intj =1; j < n; j++) {if(obstacleGrid[i][j] ==0) {? ? ? ? ? ? ? ? dp[i][j] = dp[i -1][j] + dp[i][j -1];? ? ? ? ? ? }? ? ? ? }? ? }returndp[m -1][n -1];}復制代碼
簡單說一下滾動數(shù)組的版本，當我們知道當前位置的最多路徑數(shù)時，我們去求下一個位置的路徑數(shù)，只需要知道左邊和上邊的可以了，空間復雜度為o(m)
參考代碼
publicintuniquePathsWithObstacles(int[][] obstacleGrid){intn = obstacleGrid.length, m = obstacleGrid[0].length;int[] f =newint[m];? ? f[0] = obstacleGrid[0][0] ==0?1:0;for(inti =0; i < n; ++i) {for(intj =0; j < m; ++j) {if(obstacleGrid[i][j] ==1) {? ? ? ? ? ? ? ? f[j] =0;? ? ? ? ? ? }elseif(j -1>=0&& obstacleGrid[i][j -1] ==0) {? ? ? ? ? ? ? ? f[j] += f[j -1];? ? ? ? ? ? }? ? ? ? }? ? }returnf[m -1];}復制代碼
No.10
看到這次分享的最后一題啦，能看到這里的人呀，都是人才。????????
來一道比較簡單的題目吧?。?！
leecode 64. 最小路徑和
給定一個包含非負整數(shù)的 m?x?n?網(wǎng)格?grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。
說明：每次只能向下或者向右移動一步。
示例 1：
輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因為路徑 1→3→1→1→1 的總和最小。
示例 2：
輸入：grid = [[1,2,3],[4,5,6]]
輸出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
看了之前的題解，想想就明白了，這里用動態(tài)規(guī)劃解題，考慮一下幾點：
邊界處理
中間的路徑
這里的結果會有M*N次所以每個格子的結果都會作比較，我們取較小值就可以了
dp[i][j] 表示從左上角出發(fā)到 (i,j)(i,j) 位置的最小路徑和
初始條件：dp[0][0]=grid[0][0]
當 i>0 j=0時dp[i][0]=dp[i-1][0] + grid[i][0]; // grid[i][0]為最后一個格子的值
當 i=0 j>0時dp[0][j-1]=dp[0][j-1] + grid[0][j];
當 i>0 j>0時dp[i-1][j-1]=min(dp[i-1][j],dp[i][j-1])? + grid[i][j];
參考代碼：
classSolution{publicintminPathSum(int[][] grid){if(grid ==null|| grid.length ==0|| grid[0].length ==0) {return0;? ? ? ? }introws = grid.length, columns = grid[0].length;int[][] dp =newint[rows][columns];? ? ? ? dp[0][0] = grid[0][0];for(inti =1; i < rows; i++) {? ? ? ? ? ? dp[i][0] = dp[i -1][0] + grid[i][0];? ? ? ? }for(intj =1; j < columns; j++) {? ? ? ? ? ? dp[0][j] = dp[0][j -1] + grid[0][j];? ? ? ? }for(inti =1; i < rows; i++) {for(intj =1; j < columns; j++) {? ? ? ? ? ? ? ? dp[i][j] = Math.min(dp[i -1][j], dp[i][j -1]) + grid[i][j];? ? ? ? ? ? }? ? ? ? }returndp[rows -1][columns -1];? ? }}
作者：汀雨筆記
鏈接：https://juejin.cn/post/6937193443953393700
來源：掘金
著作權歸作者所有。商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處。
