目錄
引言：
例題1：最長(zhǎng)公共子序列
例題2：不同的子序列
例題3：通配符匹配
例題4：正則表達(dá)式
結(jié)語(yǔ)：
引言：
本節(jié)我們就要進(jìn)入兩個(gè)數(shù)組的dp問題的學(xué)習(xí)，通過(guò)前面幾個(gè)章節(jié)的學(xué)習(xí)，相信友友們對(duì)動(dòng)態(tài)規(guī)劃的解題步驟和代碼編寫步驟已經(jīng)有了一定的了解(*/ω＼*)，接下來(lái)我會(huì)通過(guò)例題來(lái)幫助大家理解兩個(gè)數(shù)組dp問題的一般解題模板，那廢話不多說(shuō)我們開始吧??????！
首先我先給出這類dp問題的常見的套路和狀態(tài)表示如下：?
兩個(gè)數(shù)組的dp問題最常用的狀態(tài)表示就是dp[i][j]表示選取第一個(gè)數(shù)組的(0,i)區(qū)間以及第二個(gè)數(shù)組(0,j)區(qū)間作為研究對(duì)象，利用兩個(gè)表最后一個(gè)位置的狀況來(lái)遞推出關(guān)系，進(jìn)而填寫dp表。
例題1：最長(zhǎng)公共子序列
鏈接：最長(zhǎng)公共子序列
題目簡(jiǎn)介：
給定兩個(gè)字符串?text1?和?text2，返回這兩個(gè)字符串的最長(zhǎng)?公共子序列?的長(zhǎng)度。如果不存在?公共子序列?，返回?0?。
一個(gè)字符串的?子序列?是指這樣一個(gè)新的字符串：它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
- 例如，
"ace"?是?"abcde"?的子序列，但?"aec"?不是?"abcde"?的子序列。
兩個(gè)字符串的?公共子序列?是這兩個(gè)字符串所共同擁有的子序列。
解法（動(dòng)態(tài)規(guī)劃）：
?1. 狀態(tài)表示：
兩個(gè)數(shù)組的動(dòng)態(tài)規(guī)劃，我們的定義狀態(tài)表示的經(jīng)驗(yàn)就是：
（1）選取第?個(gè)數(shù)組[0, i] 區(qū)間以及第?個(gè)數(shù)組[0, j] 區(qū)間作為研究對(duì)象。
（2）結(jié)合題目要求，定義狀態(tài)表示。
在這道題中，我們根據(jù)定義狀態(tài)表示為：dp[i][j] 表示： s1 的[0, i] 區(qū)間以及s2 的[0, j] 區(qū)間內(nèi)的所有的子序列中，最長(zhǎng)公共子序列的長(zhǎng)度。
?2.狀態(tài)轉(zhuǎn)移方程：
分析狀態(tài)轉(zhuǎn)移方程的經(jīng)驗(yàn)就是根據(jù)最后?個(gè)位置的狀況，分情況討論：
（1）兩個(gè)字符相同， s1[i] = s2[j] ：那么最長(zhǎng)公共子序列就在s1 的[0, i - 1] 以及s2 的[0, j - 1] 區(qū)間上找到?個(gè)最長(zhǎng)的，然后再加上s1[i]即可。因此dp[i][j] = dp[i - 1][j - 1] + 1 。
（2）兩個(gè)字符不相同， s1[i] != s2[j] ：那么最長(zhǎng)公共子序列?定不會(huì)同時(shí)以s1[i]和s2[j] 結(jié)尾。那么我們找最長(zhǎng)公共子序列時(shí)，有下面三種策略：
1.去s1 的[0, i - 1] 以及s2 的[0, j] 區(qū)間內(nèi)找：此時(shí)最大長(zhǎng)度為dp[i - 1][j] 。
2.去s1 的[0, i] 以及s2 的[0, j - 1]區(qū)間內(nèi)找：此時(shí)最大長(zhǎng)度為dp[i ][j - 1]。
3.去s1 的[0, i - 1] 以及s2 的[0, j - 1]區(qū)間內(nèi)找：此時(shí)最大長(zhǎng)度為dp[i - 1][j - 1] 。
我們要三者的最大值即可。但是我們細(xì)細(xì)觀察會(huì)發(fā)現(xiàn)，第三種包含在第?種和第?種情況里面，但是我們求的是最大值，并不影響最終結(jié)果。因此只需求前兩種情況下的最大值即可。
綜上，狀態(tài)轉(zhuǎn)移方程為：
（1）if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 。
（2）if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。.
?3.初始化：
當(dāng)s1 為空時(shí)，沒有長(zhǎng)度，同理s2也是。因此第一行和第?列里面的值初始化為0即可保證后續(xù)填表是正確的。當(dāng)為字符串時(shí)可以再字符串前面添加一個(gè)空字符來(lái)對(duì)其我們的下標(biāo)，這樣我們就不用注意下標(biāo)的映射關(guān)系了。
?4.填表順序：
從上往下填寫每?行，每?行從左往右。
?5.返回值：
返回dp[m][n]。
代碼如下：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
//1.創(chuàng)建 dp 表
//2.初始化
//3.填表
//4.返回值
int n = text1.length();
int m = text2.length();
int[][] dp = new int[n + 1][m + 1];
text1 = " " + text1;
text2 = " " + text2;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(text1.charAt(i) == text2.charAt(j)){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
}
}
}
return dp[n][m];
}
}時(shí)間復(fù)雜度：O（n * m）
空間復(fù)雜度：O（n * m）
例題2：不同的子序列
鏈接：不同的子序列
題目簡(jiǎn)介：給你兩個(gè)字符串?s?和?t?，統(tǒng)計(jì)并返回在?s?的?子序列?中?t?出現(xiàn)的個(gè)數(shù)，結(jié)果需要對(duì)?109?+ 7 取模。
解法（動(dòng)態(tài)規(guī)劃）：
這題說(shuō)是要取模但是實(shí)際做不用取模也可以過(guò)。
?1. 狀態(tài)表示：
dp[i][j] 表示：在字符串 s 的 [0, j] 區(qū)間內(nèi)的所有子序列中，有多少個(gè) t 字符串 [0, i] 區(qū)間內(nèi)的子串。（兩個(gè)數(shù)組的dp問題狀態(tài)表示一般都長(zhǎng)這樣）。
?2.狀態(tài)轉(zhuǎn)移方程：
根據(jù)最后?個(gè)位置的元素來(lái)進(jìn)行分類討論和分析。
（1）當(dāng)t[i] == s[j]的時(shí)候，此時(shí)的子序列有兩種選擇：
1.?種選擇是：子序列選擇s[j]作為結(jié)尾，此時(shí)相當(dāng)于在狀態(tài)dp[i - 1][j - 1]中的所有符合要求的子序列的后面，再加上?個(gè)字符s[j]（請(qǐng)大家結(jié)合狀態(tài)表示， 好好理解這句話），此時(shí)dp[i][j] = dp[i - 1][j - 1]。不用加一，求的是個(gè)數(shù)不是長(zhǎng)度。
2.另?種選擇是：我就是任性，我就不選擇s[j]作為結(jié)尾。此時(shí)相當(dāng)于選擇了狀態(tài)dp[i][j - 1] 中所有符合要求的子序列。我們也可以理解為繼承了上個(gè)狀態(tài)里面的求得的子序列。此時(shí)dp[i][j] = dp[i][j - 1] 。
兩種情況加起來(lái)，就是 t[i] == s[j]時(shí)的結(jié)果。
（2）當(dāng)t[i] != s[j] 的時(shí)候，此時(shí)的子序列只能從dp[i][j - 1] 中選擇所有符合要求的子序列。只能繼承上個(gè)狀態(tài)里面求得的子序列， dp[i][j] = dp[i][j - 1] 。
綜上所述，狀態(tài)轉(zhuǎn)移方程為：
（1）所有情況下都可以繼承上?次的結(jié)果： dp[i][j] = dp[i][j - 1].
（2）當(dāng) t[i] == s[j]時(shí)，可以多選擇?種情況： dp[i][j] += dp[i - 1][j - 1].
?3.初始化：
輔助節(jié)點(diǎn) + 字符串前面加一個(gè)空格，這兩種初始化方法一起用。
當(dāng)s為空時(shí)，t的子串中有?個(gè)空串和它?樣，因此初始化第?行全部為1 。
?4.填表順序：
從上往下
從左往右
?5.返回值：
返回dp[m][n]的值。
代碼如下：
class Solution {
public int numDistinct(String s, String t) {
//1.創(chuàng)建 dp 表
//2.初始化
//3.填表
//4.返回值
//s大m
//t小n
int n = t.length();
int m = s.length();
int[][] dp = new int[n + 1][m + 1];
s = " " + s;
t = " " + t;
for(int i = 0;i <= m;i++){
dp[0][i] = 1;
}
for(int i = 1;i <= n;i++){
for(int j = i;j <= m;j++){
if(t.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i - 1][j - 1];
}
dp[i][j] += dp[i][j - 1];
}
}
return dp[n][m];
}
}時(shí)間復(fù)雜度：O（n * m）
空間復(fù)雜度：O（n * m）
例題3：通配符匹配
鏈接：通配符匹配
題目簡(jiǎn)介：
給你一個(gè)輸入字符串 (s) 和一個(gè)字符模式 (p) ，請(qǐng)你實(shí)現(xiàn)一個(gè)支持?'?'?和?'*'?匹配規(guī)則的通配符匹配：
-
'?'?可以匹配任何單個(gè)字符。 -
'*'?可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要條件是：字符模式必須能夠?完全匹配?輸入字符串（而不是部分匹配）。
??解法（動(dòng)態(tài)規(guī)劃）：
?1. 狀態(tài)表示：
dp[i][j] 表示： p字符串[0, j] 區(qū)間內(nèi)的子串能否匹配字符串s的 [0, i] 區(qū)間內(nèi)的子串。
?2.狀態(tài)轉(zhuǎn)移方程：
根據(jù)最后?個(gè)位置的元素來(lái)分情況討論：
（1）當(dāng)s[i] == p[j]或p[j] == '?' 的時(shí)候，此時(shí)兩個(gè)字符串匹配上了當(dāng)前的?個(gè)字符，只能從dp[i - 1][j - 1] 中看當(dāng)前字符前面的兩個(gè)子串是否匹配。只能繼承上個(gè)狀態(tài)中的匹配結(jié)果，dp[i][j] = dp[i][j - 1]?
（2）當(dāng)p[j] == '*' 的時(shí)候，此時(shí)匹配策略有兩種選擇：
1.?種選擇是： * 匹配空字符串，此時(shí)相當(dāng)于它匹配了?個(gè)寂寞，直接繼承狀態(tài)dp[i][j - 1] ，此時(shí)dp[i][j] = dp[i][j - 1] 。
2.另?種選擇是： * 向前匹配1 ~ n 個(gè)字符，直至匹配上整個(gè)s1串。此時(shí)相當(dāng)于從dp[k][j - 1]所有匹配情況中，選擇性繼承可以成功的情況。此時(shí)dp[i][j] = dp[k][j - 1]。
（3）當(dāng)p[j] 不是特殊字符，且不與s[i]相等時(shí)，無(wú)法匹配。
綜上所述，狀態(tài)轉(zhuǎn)移方程為：
（1）當(dāng)s[i] == p[j] 或p[j] == '?' 時(shí)： dp[i][j] = dp[i][j - 1].
（2）當(dāng)p[j] == '*' 時(shí)，有多種情況需要討論： dp[i][j] = dp[k][j - 1] (0 <= k <= i).
優(yōu)化：當(dāng)我們發(fā)現(xiàn)，計(jì)算?個(gè)狀態(tài)的時(shí)候，需要?個(gè)循環(huán)才能搞定的時(shí)候，我們要想到去優(yōu)化。優(yōu) 化的方向就是用?個(gè)或者兩個(gè)狀態(tài)來(lái)表示這?堆的狀態(tài)。通常就是把它寫下來(lái)，然后用數(shù)學(xué)的方式做一個(gè)等價(jià)替換。我們驚奇的發(fā)現(xiàn)， dp[i][j] 的狀態(tài)轉(zhuǎn)移方程里面除了第?項(xiàng)以外，其余的都可以用dp[i - 1][j]替代。因此，我們優(yōu)化我們的狀態(tài)轉(zhuǎn)移方程為： dp[i][j] = dp[i - 1][j] || dp[i][j - 1] 。
?3.初始化：
（1）dp[0][0]表示兩個(gè)空串能否匹配，答案是顯然的，初始化為true。
（2）第一行表示s是?個(gè)空串， p串和空串只有?種匹配可能，即p串表示會(huì)為" *** " ，此時(shí)也相當(dāng)于空串匹配上空串。所以，我們可以遍歷p串，把所有前導(dǎo)為" * " 的p子串和空串的dp值設(shè)為true。
（3）第?列表示p是?個(gè)空串，不可能匹配上s 串，跟隨數(shù)組初始化即可。
?4.填表順序：
從上往下填每一行，每一行從左往右。
?5.返回值：
返回dp[m][n]。
對(duì)應(yīng)代碼如下：
class Solution {
public boolean isMatch(String s, String p) {
//1.創(chuàng)建 dp 表
//2.初始化
//3.填表
//4.返回值
//s為n
//p為m
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
s = " " + s;
p = " " + p;
boolean tmp = true;
dp[0][0] = true;
for(int i = 1;i <= m;i++){
if(p.charAt(i) != '*'){
tmp = false;
}
dp[0][i] = tmp;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(p.charAt(j) == '?'){
dp[i][j] = dp[i - 1][j - 1];
}else if(p.charAt(j) == '*'){
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}else{
dp[i][j] = (s.charAt(i) == p.charAt(j)) && dp[i -1][j - 1];
}
}
}
return dp[n][m];
}
}例題4：正則表達(dá)式
鏈接：正則表達(dá)式
題目簡(jiǎn)介：
給你一個(gè)字符串?s?和一個(gè)字符規(guī)律?p，請(qǐng)你來(lái)實(shí)現(xiàn)一個(gè)支持?'.'?和?'*'?的正則表達(dá)式匹配。
-
'.'?匹配任意單個(gè)字符 -
'*'?匹配零個(gè)或多個(gè)前面的那一個(gè)元素
所謂匹配，是要涵蓋?整個(gè)?字符串?s的，而不是部分字符串。
解法（動(dòng)態(tài)規(guī)劃）：
?1. 狀態(tài)表示：
dp[i][j] 表示：字符串p的[0, j]區(qū)間和字符串s的[0, i]區(qū)間是否可以匹配。
?2.狀態(tài)轉(zhuǎn)移方程：
（1）當(dāng)s[i] == p[j] 或p[j] == '.' 的時(shí)候，此時(shí)兩個(gè)字符串匹配上了當(dāng)前的?個(gè)字符， 只能從dp[i - 1][j - 1] 中看當(dāng)前字符前面的兩個(gè)子串是否匹配。只能繼承上個(gè)狀態(tài)中的匹配結(jié)果， dp[i][j] = dp[i - 1][j - 1]。
（2）當(dāng)p[j] == '*' 的時(shí)候，和上道題稍有不同的是，上道題"*" 本身便可匹配0 ~ n 個(gè)字符，但此題是要帶著p[j - 1]的字符?起，匹配0 ~ n 個(gè)和p[j - 1] 相同的字符。此時(shí)，匹配策略有兩種選擇：
1.?種選擇是： p[j - 1]* 匹配空字符串，此時(shí)相當(dāng)于兩個(gè)字符串什么都沒有匹配，直接繼承狀態(tài)dp[i][j - 2] ，此時(shí)dp[i][j] = dp[i][j - 2]。
2.另?種選擇是： p[j - 1]* 向前匹配1 ~ n 個(gè)字符，直至匹配上整個(gè)s1串。此時(shí)相當(dāng)于從dp[k][j - 2] 中所有匹配情況中，選擇性繼承可以成功的情況。此時(shí)dp[i][j] = dp[k][j - 2]。
（3）當(dāng)p[j] 不是特殊字符，且不與s[i]相等時(shí)，無(wú)法匹配。
綜上所述，狀態(tài)轉(zhuǎn)移方程為：
（1）當(dāng)s[i] == p[j] 或p[j] == '.' 時(shí)： dp[i][j] = dp[i][j - 1].
（2）當(dāng)p[j] == '*' 時(shí)，有多種情況需要討論： dp[i][j] = dp[i][j - 2] ； dp[i][j] = dp[k][j - 1].
優(yōu)化和第三題一樣也是用等價(jià)替換，把后面多種情況歸結(jié)成一種表達(dá)式。
?3.初始化：
第一行表示s 是?個(gè)空串， p 串和空串只有?種匹配可能，即p串全部字符表示為"任?字符?+ * "，此時(shí)也相當(dāng)于空串匹配上空串。所以，我們可以遍歷p串，把所有前導(dǎo)為"任?字符+ * "?的p子串和空串的dp值設(shè)為true。
for(int i = 2;i <= m;i += 2){
if(p.charAt(i) != '*'){
break;
}
dp[0][i] = true;
}?4.填表順序：
從上往下填每一行，每一行從左往右。
?5.返回值：
?根據(jù)狀態(tài)表示，返回dp[m][n]的值。
代碼如下：
class Solution {
public boolean isMatch(String s, String p) {
//1.創(chuàng)建 dp 表
//2.初始化
//3.填表
//4.返回值
//s為n
//p為m
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
s = " " + s;
p = " " + p;
for(int i = 2;i <= m;i += 2){
if(p.charAt(i) != '*'){
break;
}
dp[0][i] = true;
}
dp[0][0] = true;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(p.charAt(j) != '*'){
dp[i][j] = (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) &&
dp[i - 1][j - 1];
}else{
dp[i][j] = (dp[i][j - 2]) || (p.charAt(j - 1) == s.charAt(i)
|| p.charAt(j - 1) == '.') && dp[i - 1][j];
}
}
}
return dp[n][m];
}
}結(jié)語(yǔ)：
其實(shí)寫博客不僅僅是為了教大家，同時(shí)這也有利于我鞏固知識(shí)點(diǎn)，和做一個(gè)學(xué)習(xí)的總結(jié)，由于作者水平有限，對(duì)文章有任何問題還請(qǐng)指出，非常感謝。如果大家有所收獲的話還請(qǐng)不要吝嗇你們的點(diǎn)贊收藏和關(guān)注，這可以激勵(lì)我寫出更加優(yōu)秀的文章。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-842377.html
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-842377.html
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃課堂7-----兩個(gè)數(shù)組的dp問題（等價(jià)代換）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
