案例二：二維數(shù)組的 DP

我做了幾十道 DP 的算法題，可以說，80% 的題，都是要用二維數(shù)組的，所以下面的題主要以二維數(shù)組為主，當(dāng)然有人可能會說，要用一維還是二維，我怎么知道？這個問題不大，接著往下看。

問題描述

一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。

問總共有多少條不同的路徑？

還是老樣子，三個步驟來解決。

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

由于我們的目的是從左上角到右下角一共有多少種路徑，那我們就定義 dp[i] [j]的含義為：當(dāng)機器人從左上角走到(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)系式

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

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

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

因為是計算所有可能的步驟，所以是把所有可能走的路徑都加起來，所以關(guān)系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

步驟三、找出初始值

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

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

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

擼代碼

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

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

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

問題描述

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

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

舉例：
輸入:
arr = [
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。

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

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

由于我們的目的是從左上角到右下角，最小路徑和是多少，那我們就定義 dp[i] [j]的含義為：當(dāng)機器人從左上角走到(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)系式

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

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

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

不過這次不是計算所有可能路徑，而是計算哪一個路徑和是最小的，那么我們要從這兩種方式中，選擇一種，使得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)系式嗎？答是不能的，因為這個時候把 i - 1 或者 j - 1，就變成負數(shù)了，數(shù)組就會出問題了，所以我們的初始值是計算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。這個還是非常容易計算的，相當(dāng)于計算機圖中的最上面一行和左邊一列。因此初始值如下：

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

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

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ù) 。

你可以對一個單詞進行如下三種操作：

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

示例 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)系了，比起其他題，這道題相對比較難找一點，但是，不管多難找，大部分情況下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某種關(guān)系。因為我們的目標(biāo)就是，從規(guī)模小的，通過一些操作，推導(dǎo)出規(guī)模大的。對于這道題，我們可以對 word1 進行三種操作

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

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

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

b、如果我們 word1[i] 與 word2 [j] 不相等，這個時候我們就必須進行調(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)系式嗎？答是不能的，因為這個時候把 i - 1 或者 j - 1，就變成負數(shù)了，數(shù)組就會出問題了，所以我們的初始值是計算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。這個還是非常容易計算的，因為當(dāng)有一個字符串的長度為 0 時，轉(zhuǎ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;
自我介紹一下，小編13年上海交大畢業(yè)，曾經(jīng)在小公司待過，也去過華為、OPPO等大廠，18年進入阿里一直到現(xiàn)在。

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

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

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

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

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

最后

針對Android程序員，我這邊給大家整理了一些資料，包括不限于高級UI、性能優(yōu)化、架構(gòu)師課程、NDK、混合式開發(fā)（ReactNative+Weex）微信小程序、Flutter等全方面的Android進階實踐技術(shù)；希望能幫助到大家，也節(jié)省大家在網(wǎng)上搜索資料的時間來學(xué)習(xí)，也可以分享動態(tài)給身邊好友一起學(xué)習(xí)！

• Android前沿技術(shù)大綱

  

• 全套體系化高級架構(gòu)視頻

  

Android高級架構(gòu)資料、源碼、筆記、視頻。高級UI、性能優(yōu)化、架構(gòu)師課程、混合式開發(fā)（ReactNative+Weex）全方面的Android進階實踐技術(shù)，群內(nèi)還有技術(shù)大牛一起討論交流解決問題。

《互聯(lián)網(wǎng)大廠面試真題解析、進階開發(fā)核心學(xué)習(xí)筆記、全套講解視頻、實戰(zhàn)項目源碼講義》點擊傳送門即可獲??！文章來源地址http://www.zghlxwxcb.cn/news/detail-858536.html

…(img-lNXznL5u-1713303953246)]

Android高級架構(gòu)資料、源碼、筆記、視頻。高級UI、性能優(yōu)化、架構(gòu)師課程、混合式開發(fā)（ReactNative+Weex）全方面的Android進階實踐技術(shù)，群內(nèi)還有技術(shù)大牛一起討論交流解決問題。

《互聯(lián)網(wǎng)大廠面試真題解析、進階開發(fā)核心學(xué)習(xí)筆記、全套講解視頻、實戰(zhàn)項目源碼講義》點擊傳送門即可獲??！

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