一種是從 (i-1, j) 這個位置走一步到達(dá)

一種是從(i, j - 1) 這個位置走一步到達(dá)

因?yàn)槭怯嬎闼锌赡艿牟襟E，所以是把所有可能走的路徑都加起來，所以關(guān)系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

步驟三、找出初始值

顯然，當(dāng) dp[i] [j] 中，如果 i 或者 j 有一個為 0，那么還能使用關(guān)系式嗎？答是不能的，因?yàn)檫@個時候把 i - 1 或者 j - 1，就變成負(fù)數(shù)了，數(shù)組就會出問題了，所以我們的初始值是計算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。這個還是非常容易計算的，相當(dāng)于計算機(jī)圖中的最上面一行和左邊一列。因此初始值如下：

dp[0] [0….n-1] = 1; // 相當(dāng)于最上面一行，機(jī)器人只能一直往左走

dp[0…m-1] [0] = 1; // 相當(dāng)于最左面一列，機(jī)器人只能一直往下走

擼代碼

三個步驟都寫出來了，直接看代碼

public static int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}

int[][] dp = new int[m][n]; //
// 初始化
for(int i = 0; i < m; i++){
dp[i][0] = 1;
}
for(int i = 0; i < n; i++){
dp[0][i] = 1;
}
// 推導(dǎo)出 dp[m-1][n-1]
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}

案例三、二維數(shù)組 DP

寫到這里，有點(diǎn)累了，，但還是得寫下去，所以看的小伙伴，你們可得繼續(xù)看呀。下面這道題也不難，比上面的難一丟丟，不過也是非常類似

問題描述

給定一個包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說明：每次只能向下或者向右移動一步。

舉例：
輸入:
arr = [
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。

和上面的差不多，不過是算最優(yōu)路徑和，

步驟一、定義數(shù)組元素的含義

由于我們的目的是從左上角到右下角，最小路徑和是多少，那我們就定義 dp[i] [j]的含義為：當(dāng)機(jī)器人從左上角走到(i, j) 這個位置時，最下的路徑和是 dp[i] [j]。那么，dp[m-1] [n-1] 就是我們要的答案了。

注意，這個網(wǎng)格相當(dāng)于一個二維數(shù)組，數(shù)組是從下標(biāo)為 0 開始算起的，所以 由下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我們要走的答案。

步驟二：找出關(guān)系數(shù)組元素間的關(guān)系式

想象以下，機(jī)器人要怎么樣才能到達(dá) (i, j) 這個位置？由于機(jī)器人可以向下走或者向右走，所以有兩種方式到達(dá)

一種是從 (i-1, j) 這個位置走一步到達(dá)

一種是從(i, j - 1) 這個位置走一步到達(dá)

不過這次不是計算所有可能路徑，而是計算哪一個路徑和是最小的，那么我們要從這兩種方式中，選擇一種，使得dp[i] [j] 的值是最小的，顯然有
dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j];// arr[i][j] 表示網(wǎng)格種的值
步驟三、找出初始值

顯然，當(dāng) dp[i] [j] 中，如果 i 或者 j 有一個為 0，那么還能使用關(guān)系式嗎？答是不能的，因?yàn)檫@個時候把 i - 1 或者 j - 1，就變成負(fù)數(shù)了，數(shù)組就會出問題了，所以我們的初始值是計算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。這個還是非常容易計算的，相當(dāng)于計算機(jī)圖中的最上面一行和左邊一列。因此初始值如下：

dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相當(dāng)于最上面一行，機(jī)器人只能一直往左走

dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相當(dāng)于最左面一列，機(jī)器人只能一直往下走
代碼如下

public static int uniquePaths(int[][] arr) {
int m = arr.length;
int n = arr[0].length;
if (m <= 0 || n <= 0) {
return 0;
}

int[][] dp = new int[m][n]; //
// 初始化
dp[0][0] = arr[0][0];
// 初始化最左邊的列
for(int i = 1; i < m; i++){
dp[i][0] = dp[i-1][0] + arr[i][0];
}
// 初始化最上邊的行
for(int i = 1; i < n; i++){
dp[0][i] = dp[0][i-1] + arr[0][i];
}
// 推導(dǎo)出 dp[m-1][n-1]
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
}
}
return dp[m-1][n-1];
}

案例 4：編輯距離

這次給的這道題比上面的難一些，在 leetcdoe 的定位是 hard 級別。

問題描述

給定兩個單詞 word1 和 word2，計算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。

你可以對一個單詞進(jìn)行如下三種操作：

插入一個字符
刪除一個字符
替換一個字符

示例 1:
輸入: word1 = “horse”, word2 = “ros”
輸出: 3
解釋:
horse -> rorse (將 ‘h’ 替換為 ‘r’)
rorse -> rose (刪除 ‘r’)
rose -> ros (刪除 ‘e’)

解答

還是老樣子，按照上面三個步驟來，并且我這里可以告訴你，90% 的字符串問題都可以用動態(tài)規(guī)劃解決，并且90%是采用二維數(shù)組。

步驟一、定義數(shù)組元素的含義

由于我們的目的求將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。那我們就定義 dp[i] [j]的含義為：當(dāng)字符串 word1 的長度為 i，字符串 word2 的長度為 j 時，將 word1 轉(zhuǎn)化為 word2 所使用的最少操作次數(shù)為 dp[i] [j]。

有時候，數(shù)組的含義并不容易找，所以還是那句話，我給你們一個套路，剩下的還得看你們?nèi)ヮI(lǐng)悟。

步驟二：找出關(guān)系數(shù)組元素間的關(guān)系式

接下來我們就要找 dp[i] [j] 元素之間的關(guān)系了，比起其他題，這道題相對比較難找一點(diǎn)，但是，不管多難找，大部分情況下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某種關(guān)系。因?yàn)槲覀兊哪繕?biāo)就是，從規(guī)模小的，通過一些操作，推導(dǎo)出規(guī)模大的。對于這道題，我們可以對 word1 進(jìn)行三種操作

插入一個字符
刪除一個字符
替換一個字符

由于我們是要讓操作的次數(shù)最小，所以我們要尋找最佳操作。那么有如下關(guān)系式：

a、如果我們 word1[i] 與 word2 [j] 相等，這個時候不需要進(jìn)行任何操作，顯然有 dp[i] [j] = dp[i-1] [j-1]。（別忘了 dp[i] [j] 的含義哈）。

b、如果我們 word1[i] 與 word2 [j] 不相等，這個時候我們就必須進(jìn)行調(diào)整，而調(diào)整的操作有 3 種，我們要選擇一種。三種操作對應(yīng)的關(guān)系試如下（注意字符串與字符的區(qū)別）：
（1）、如果把字符 word1[i] 替換成與 word2[j] 相等，則有 dp[i] [j] = dp[i-1] [j-1] + 1;

（2）、如果在字符串 word1末尾插入一個與 word2[j] 相等的字符，則有 dp[i] [j] = dp[i] [j-1] + 1;

（3）、如果把字符 word1[i] 刪除，則有 dp[i] [j] = dp[i-1] [j] + 1;

那么我們應(yīng)該選擇一種操作，使得 dp[i] [j] 的值最小，顯然有

dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1;

于是，我們的關(guān)系式就推出來了，

步驟三、找出初始值

顯然，當(dāng) dp[i] [j] 中，如果 i 或者 j 有一個為 0，那么還能使用關(guān)系式嗎？答是不能的，因?yàn)檫@個時候把 i - 1 或者 j - 1，就變成負(fù)數(shù)了，數(shù)組就會出問題了，所以我們的初始值是計算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。這個還是非常容易計算的，因?yàn)楫?dāng)有一個字符串的長度為 0 時，轉(zhuǎn)化為另外一個字符串，那就只能一直進(jìn)行插入或者刪除操作了。

代碼如下（可以左右滑動）

public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
// dp[0][0…n2]的初始值
for (int j = 1; j <= n2; j++)
dp[0][j] = dp[0][j - 1] + 1;
// dp[0…n1][0] 的初始值
for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
// 通過公式推出 dp[n1][n2]
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
// 如果 word1[i] 與 word2[j] 相等。第 i 個字符對應(yīng)下標(biāo)是 i-1
if (word1.charAt(i - 1) == word2.charAt(j - 1)){
p[i][j] = dp[i - 1][j - 1];
}else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
}
return dp[n1][n2];
}

最后說下，如果你要練習(xí)，可以去 leetcode，選擇動態(tài)規(guī)劃專題，然后連續(xù)刷幾十道，保證你以后再也不怕動態(tài)規(guī)劃了。當(dāng)然，遇到很難的，咱還是得掛。

三、總結(jié)

上面的這些題，基本都是不怎么難的入門題，除了最后一道相對難一點(diǎn)，本來是要在寫幾道難一點(diǎn)，并且講如何優(yōu)化的，不過看了下字?jǐn)?shù)，文章有點(diǎn)長了，關(guān)于如何優(yōu)化的，后面再講吧，在之后的文章中，我也會按照這個步驟，在給大家講四五道動態(tài)規(guī)劃 hard 級別的題，會放在每天推文的第二條給大家學(xué)習(xí)。如果大家感興趣，文章看的人多，那么優(yōu)化篇很快就會擼出來，不過感興趣的人很少的話，動力比較少，可能就會慢一些，所以各位小伙伴，如果覺得有收獲，不妨三連走起來，嘻嘻。

自我介紹一下，小編13年上海交大畢業(yè)，曾經(jīng)在小公司待過，也去過華為、OPPO等大廠，18年進(jìn)入阿里一直到現(xiàn)在。

深知大多數(shù)初中級Android工程師，想要提升技能，往往是自己摸索成長或者是報班學(xué)習(xí)，但對于培訓(xùn)機(jī)構(gòu)動則近萬的學(xué)費(fèi)，著實(shí)壓力不小。自己不成體系的自學(xué)效果低效又漫長，而且極易碰到天花板技術(shù)停滯不前！

因此收集整理了一份《2024年Android移動開發(fā)全套學(xué)習(xí)資料》，初衷也很簡單，就是希望能夠幫助到想自學(xué)提升又不知道該從何學(xué)起的朋友，同時減輕大家的負(fù)擔(dān)。

既有適合小白學(xué)習(xí)的零基礎(chǔ)資料，也有適合3年以上經(jīng)驗(yàn)的小伙伴深入學(xué)習(xí)提升的進(jìn)階課程，基本涵蓋了95%以上Android開發(fā)知識點(diǎn)，真正體系化！

由于文件比較大，這里只是將部分目錄截圖出來，每個節(jié)點(diǎn)里面都包含大廠面經(jīng)、學(xué)習(xí)筆記、源碼講義、實(shí)戰(zhàn)項目、講解視頻，并且會持續(xù)更新！

如果你覺得這些內(nèi)容對你有幫助，可以掃碼獲?。。。▊渥ⅲ篈ndroid）

文末

今天關(guān)于面試的分享就到這里，還是那句話，有些東西你不僅要懂，而且要能夠很好地表達(dá)出來，能夠讓面試官認(rèn)可你的理解，例如Handler機(jī)制，這個是面試必問之題。有些晦澀的點(diǎn)，或許它只活在面試當(dāng)中，實(shí)際工作當(dāng)中你壓根不會用到它，但是你要知道它是什么東西。

最后在這里小編分享一份自己收錄整理上述技術(shù)體系圖相關(guān)的幾十套騰訊、頭條、阿里、美團(tuán)等公司2021年的面試題，把技術(shù)點(diǎn)整理成了視頻和PDF（實(shí)際上比預(yù)期多花了不少精力），包含知識脈絡(luò) + 諸多細(xì)節(jié)，由于篇幅有限，這里以圖片的形式給大家展示一部分。

還有?高級架構(gòu)技術(shù)進(jìn)階腦圖、Android開發(fā)面試專題資料，高級進(jìn)階架構(gòu)資料 幫助大家學(xué)習(xí)提升進(jìn)階，也節(jié)省大家在網(wǎng)上搜索資料的時間來學(xué)習(xí)，也可以分享給身邊好友一起學(xué)習(xí)。

【Android核心高級技術(shù)PDF文檔，BAT大廠面試真題解析】

【算法合集】

【延伸Android必備知識點(diǎn)】

【Android部分高級架構(gòu)視頻學(xué)習(xí)資源】

**Android精講視頻領(lǐng)取學(xué)習(xí)后更加是如虎添翼！**進(jìn)軍BATJ大廠等（備戰(zhàn)）！現(xiàn)在都說互聯(lián)網(wǎng)寒冬，其實(shí)無非就是你上錯了車，且穿的少（技能），要是你上對車，自身技術(shù)能力夠強(qiáng)，公司換掉的代價大，怎么可能會被裁掉，都是淘汰末端的業(yè)務(wù)Curd而已！現(xiàn)如今市場上初級程序員泛濫，這套教程針對Android開發(fā)工程師1-6年的人員、正處于瓶頸期，想要年后突破自己漲薪的，進(jìn)階Android中高級、架構(gòu)師對你更是如魚得水，趕快領(lǐng)取吧！

《Android學(xué)習(xí)筆記總結(jié)+移動架構(gòu)視頻+大廠面試真題+項目實(shí)戰(zhàn)源碼》，點(diǎn)擊傳送門即可獲??！

，其實(shí)無非就是你上錯了車，且穿的少（技能），要是你上對車，自身技術(shù)能力夠強(qiáng)，公司換掉的代價大，怎么可能會被裁掉，都是淘汰末端的業(yè)務(wù)Curd而已！現(xiàn)如今市場上初級程序員泛濫，這套教程針對Android開發(fā)工程師1-6年的人員、正處于瓶頸期，想要年后突破自己漲薪的，進(jìn)階Android中高級、架構(gòu)師對你更是如魚得水，趕快領(lǐng)取吧！文章來源地址http://www.zghlxwxcb.cn/news/detail-846750.html

《Android學(xué)習(xí)筆記總結(jié)+移動架構(gòu)視頻+大廠面試真題+項目實(shí)戰(zhàn)源碼》，點(diǎn)擊傳送門即可獲?。?/strong>

到了這里，關(guān)于LC狂刷66道Dynamic-Programming算法題。跟動態(tài)規(guī)劃說拜拜的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！