告別動態規劃，連刷 40 道題，我總結了這些套路，看不懂你打我（萬字長文）
動態規劃難嗎？說實話，我覺得很難，特別是對於
初學者
來說，我當時入門動態規劃的時候，是看 0-1 揹包問題，當時真的是一臉懵逼。後來，我遇到動態規劃的題，
看的懂答案，但就是自己不會做，不知道怎麼下手
。就像做遞迴的題，看的懂答案，但下不了手，關於遞迴的，我之前也寫過一篇
套路
的文章，如果對遞迴不大懂的，強烈建議看一看：為什麼你學不會遞迴，告別遞迴，談談我的經驗
對於動態規劃，春招秋招時好多題都會用到動態規劃，一氣之下，再 leetcode 連續刷了幾十道題
之後，豁然開朗 ，感覺動態規劃也不是很難，今天，我就來跟大家講一講，我是怎麼做動態規劃的題的，以及從中學到的一些
套路
。相信你看完一定有所收穫
如果你對動態規劃感興趣，或者你看的懂動態規劃，但卻不知道怎麼下手，那麼我建議你好好看以下，這篇文章的寫法，和之前那篇講遞迴的寫法，是差不多一樣的，將會舉大量的例子。如果一次性看不完，建議收藏，同時別忘了
素質三連
。
為了兼顧初學者，我會從最簡單的題講起，後面會越來越難，最後面還會講解，該如何最佳化。因為 80% 的動規都是可以進行最佳化的。不過我得說，如果你連動態規劃是什麼都沒聽過，可能這篇文章你也會壓力山大。
一、動態規劃的三大步驟
動態規劃，無非就是利用
歷史記錄
，來避免我們的重複計算。而這些
歷史記錄
，我們得需要一些
變數
來儲存，一般是用
一維陣列
或者
二維陣列
來儲存。下面我們先來講下做動態規劃題很重要的三個步驟，
如果你聽不懂，也沒關係，下面會有很多例題講解，估計你就懂了。之所以不配合例題來講這些步驟，也是為了怕你們腦袋亂了
第一步驟
：定義
陣列元素的含義
，上面說了，我們會用一個數組，來儲存歷史陣列，假設用一維陣列 dp［］ 吧。這個時候有一個非常非常重要的點，就是規定你這個陣列元素的含義，例如你的 dp［i］ 是代表什麼意思？
第二步驟
：找出
陣列元素之間的關係式
，我覺得動態規劃，還是有一點類似於我們高中學習時的
歸納法
的，當我們要計算 dp［n］ 時，是可以利用 dp［n-1］，dp［n-2］。。。。。dp［1］，來推出 dp［n］ 的，也就是可以利用
歷史資料
來推出新的元素值，所以我們要找出陣列元素之間的關係式，例如 dp［n］ = dp［n-1］ + dp［n-2］，這個就是他們的
關係式
了。而這一步，也是最難的一步，後面我會講幾種型別的題來說。
學過動態規劃的可能都經常聽到
最優子結構
，把大的問題拆分成小的問題，說時候，最開始的時候，我是對
最優子結構
一夢懵逼的。估計你們也聽多了，所以這一次，我將
換一種形式來講，不再是各種子問題，各種最優子結構
。所以大佬可別噴我再亂講，因為我說了，這是我自己平時做題的套路。
第三步驟
：找出
初始值
。學過
數學歸納法
的都知道，雖然我們知道了陣列元素之間的關係式，例如 dp［n］ = dp［n-1］ + dp［n-2］，我們可以透過 dp［n-1］ 和 dp［n-2］ 來計算 dp［n］，但是，我們得知道初始值啊，例如一直推下去的話，會由 dp［3］ = dp［2］ + dp［1］。而 dp［2］ 和 dp［1］ 是不能再分解的了，所以我們必須要能夠直接獲得 dp［2］ 和 dp［1］ 的值，而這，就是
所謂的初始值
。
由了
初始值
，並且有了
陣列元素之間的關係式
，那麼我們就可以得到 dp［n］ 的值了，而 dp［n］ 的含義是由你來定義的，你想
求什麼，就定義它是什麼
，這樣，這道題也就解出來了。
不懂？沒事，我們來看三四道例題
，我講嚴格按這個步驟來給大家講解。
二、案例詳解
案例一、簡單的一維 DP
問題描述：一隻青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
（1）、定義陣列元素的含義
按我上面的步驟說的，首先我們來定義 dp［i］ 的含義，我們的問題是要求青蛙跳上 n 級的臺階總共由多少種跳法，那我們就定義 dp［i］ 的含義為：
跳上一個 i 級的臺階總共有 dp[i] 種跳法
。這樣，如果我們能夠算出 dp［n］，不就是我們要求的答案嗎？所以第一步定義完成。
（2）、找出陣列元素間的關係式
我們的目的是要求 dp［n］，動態規劃的題，如你們經常聽說的那樣，就是把一個
規模
比較大的問題分成幾個
規模
比較小的問題，然後由小的問題推匯出大的問題。也就是說，dp［n］ 的規模為 n，比它規模小的是 n-1， n-2， n-3。。。。 也就是說，dp［n］ 一定會和 dp［n-1］， dp［n-2］。。。。存在某種關係的。我們要找出他們的關係。
那麼問題來了，怎麼找？
這個怎麼找，
是最核心最難的一個
，我們必須回到問題本身來了，來尋找他們的關係式，dp［n］ 究竟會等於什麼呢？
對於這道題，由於情況可以選擇跳一級，也可以選擇跳兩級，所以青蛙到達第 n 級的臺階有兩種方式
一種是從第 n-1 級跳上來
一種是從第 n-2 級跳上來
由於我們是要算
所有可能的跳法的
，所以有 dp［n］ = dp［n-1］ + dp［n-2］。
（3）、找出初始條件
當 n = 1 時，dp［1］ = dp［0］ + dp［-1］，而我們是陣列是不允許下標為負數的，所以對於 dp［1］，我們必須要
直接給出它的數值
，相當於初始值，顯然，dp［1］ = 1。一樣，dp［0］ = 0。（因為 0 個臺階，那肯定是 0 種跳法了）。於是得出初始值：
dp［0］ = 0。 dp［1］ = 1。 即 n <= 1 時，dp［n］ = n。
三個步驟都做出來了，那麼我們就來寫程式碼吧，程式碼會詳細註釋滴。
int
f
（
int
n
）{
if
（
n
<=
1
）
return
n
；
// 先建立一個數組來儲存歷史資料
int
［］
dp
=
new
int
［
n
+
1
］；
// 給出初始值
dp
［
0
］
=
0
；
dp
［
1
］
=
1
；
// 透過關係式來計算出 dp［n］
for
（
int
i
=
2
；
i
<=
n
；
i
++）{
dp
［
i
］
=
dp
［
i
-
1
］
+
dp
［
i
-
2
］；
}
// 把最終結果返回
return
dp
［
n
］；
}
（4）、再說初始化
大家先想以下，你覺得，上面的程式碼有沒有問題？
答是有問題的，還是錯的，錯在
對初始值的尋找不夠嚴謹
，這也是我故意這樣弄的，意在告訴你們，關於
初始值的嚴謹性
。例如對於上面的題，當 n = 2 時，dp［2］ = dp［1］ + dp［0］ = 1。這顯然是錯誤的，你可以模擬一下，應該是 dp［2］ = 2。
也就是說，在尋找初始值的時候，一定要注意不要找漏了，dp［2］ 也算是一個初始值，不能透過公式計算得出。有人可能會說，我想不到怎麼辦？這個很好辦，多做幾道題就可以了。
下面我再列舉三道不同的例題，並且，再在未來的文章中，我也會持續按照這個步驟，給大家找幾道有難度且型別不同的題。下面這幾道例題，不會講的特性詳細哈。實際上 ，上面的一維陣列是可以把空間最佳化成更小的，不過我們現在先不講最佳化的事，下面的題也是，不講最佳化版本。
案例二：二維陣列的 DP
我做了幾十道 DP 的演算法題，可以說，80% 的題，都是要用二維陣列的，所以下面的題主要以二維陣列為主，當然有人可能會說，要用一維還是二維，我怎麼知道？這個問題不大，接著往下看。
問題描述
一個
機器人
位於一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。
問總共有多少條不同的路徑？
這是 leetcode 的 62 號題：
https：//
leetcode-cn。com/problem
s/unique-paths/
還是老樣子，三個步驟來解決。
步驟一、定義陣列元素的含義
由於我們的目的是從左上角到右下角一共有多少種路徑，那我們就定義 dp［i］ ［j］的含義為：
當機器人從左上角走到(i, j) 這個位置時，一共有 dp[i] [j] 種路徑
。那麼，dp［m-1］ ［n-1］ 就是我們要的答案了。
注意，這個網格相當於一個二維陣列，陣列是從下標為 0 開始算起的，所以 右下角的位置是 （m-1， n - 1），所以 dp［m-1］ ［n-1］ 就是我們要找的答案。
步驟二：找出關係陣列元素間的關係式
想象以下，機器人要怎麼樣才能到達 （i， j） 這個位置？由於機器人可以向下走或者向右走，所以有兩種方式到達
一種是從 （i-1， j） 這個位置走一步到達
一種是從（i， j - 1） 這個位置走一步到達
因為是計算所有可能的步驟，所以是把所有可能走的路徑都加起來，所以關係式是 dp［i］ ［j］ = dp［i-1］ ［j］ + dp［i］ ［j-1］。
步驟三、找出初始值
顯然，當 dp［i］ ［j］ 中，如果 i 或者 j 有一個為 0，那麼還能使用關係式嗎？答是不能的，因為這個時候把 i - 1 或者 j - 1，就變成負數了，陣列就會出問題了，所以我們的初始值是計算出所有的 dp［0］ ［0…。n-1］ 和所有的 dp［0…。m-1］ ［0］。這個還是非常容易計算的，相當於計算機圖中的最上面一行和左邊一列。因此初始值如下：
dp［0］ ［0…。n-1］ = 1； // 相當於最上面一行，機器人只能一直往右走
dp［0…m-1］ ［0］ = 1； // 相當於最左面一列，機器人只能一直往下走
擼程式碼
三個步驟都寫出來了，直接看程式碼
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
；
}
// 推匯出 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
］；
}
O（n*m） 的空間複雜度可以最佳化成 O（min（n， m）） 的空間複雜度的，不過這裡先不講
案例三、二維陣列 DP
寫到這裡，有點累了，，但還是得寫下去，所以看的小夥伴，你們可得繼續看呀。下面這道題也不難，比上面的難一丟丟，不過也是非常類似
問題描述
給定一個包含非負整數的
m
x
n
網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。
說明：
每次只能向下或者向右移動一步。
舉例
：
輸入：
arr
=
［
［
1
，
3
，
1
］，
［
1
，
5
，
1
］，
［
4
，
2
，
1
］
］
輸出：
7
解釋：
因為路徑
1
→
3
→
1
→
1
→
1
的總和最小
。
和上面的差不多，不過是算最優路徑和，這是 leetcode 的第64題：
https：//
leetcode-cn。com/problem
s/minimum-path-sum/
還是老樣子，可能有些人都看煩了，哈哈，但我還是要按照步驟來寫，讓那些不大懂的加深理解。有人可能覺得，這些題太簡單了吧，別慌，小白先入門，這些屬於 medium 級別的，後面在給幾道 hard 級別的。
步驟一、定義陣列元素的含義
由於我們的目的是從左上角到右下角，最小路徑和是多少，那我們就定義 dp［i］ ［j］的含義為：
當機器人從左上角走到(i, j) 這個位置時，最下的路徑和是 dp[i] [j]
。那麼，dp［m-1］ ［n-1］ 就是我們要的答案了。
注意，這個網格相當於一個二維陣列，陣列是從下標為 0 開始算起的，所以 由下角的位置是 （m-1， n - 1），所以 dp［m-1］ ［n-1］ 就是我們要走的答案。
步驟二：找出關係陣列元素間的關係式
想象以下，機器人要怎麼樣才能到達 （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
］
表示網格種的值
步驟三、找出初始值
顯然，當 dp［i］ ［j］ 中，如果 i 或者 j 有一個為 0，那麼還能使用關係式嗎？答是不能的，因為這個時候把 i - 1 或者 j - 1，就變成負數了，陣列就會出問題了，所以我們的初始值是計算出所有的 dp［0］ ［0…。n-1］ 和所有的 dp［0…。m-1］ ［0］。這個還是非常容易計算的，相當於計算機圖中的最上面一行和左邊一列。因此初始值如下：
dp［0］ ［j］ = arr［0］ ［j］ + dp［0］ ［j-1］； // 相當於最上面一行，機器人只能一直往左走
dp［i］ ［0］ = arr［i］ ［0］ + dp［i］ ［0］； // 相當於最左面一列，機器人只能一直往下走
程式碼如下
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
］；
}
// 推匯出 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
］；
}
O（n*m） 的
空間複雜度
可以最佳化成 O（min（n， m）） 的空間複雜度的，不過這裡先不講
案例 4：編輯距離
這次給的這道題比上面的難一些，在 leetcdoe 的定位是 hard 級別。好像是 leetcode 的第 72 號題。
問題描述
給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少運算元 。
你可以對一個單詞進行如下三種操作：
插入一個字元 刪除一個字元 替換一個字元
示例
：
輸入：
word1
=
“horse”
，
word2
=
“ros”
輸出：
3
解釋：
horse
->
rorse
（
將
‘h’
替換為
‘r’
）
rorse
->
rose
（
刪除
‘r’
）
rose
->
ros
（
刪除
‘e’
）
解答
還是老樣子，按照上面三個步驟來，並且我這裡可以告訴你，90% 的字串問題都可以用動態規劃解決，並且90%是採用二維陣列。
步驟一、定義陣列元素的含義
由於我們的目的求將 word1 轉換成 word2 所使用的最少運算元 。那我們就定義 dp［i］ ［j］的含義為：
當字串 word1 的長度為 i，字串 word2 的長度為 j 時，將 word1 轉化為 word2 所使用的最少操作次數為 dp[i] [j]
。
有時候，陣列的含義並不容易找，所以還是那句話，我給你們一個套路，剩下的還得看你們去領悟。
步驟二：找出關係陣列元素間的關係式
接下來我們就要找 dp［i］ ［j］ 元素之間的關係了，比起其他題，這道題相對比較難找一點，但是，不管多難找，大部分情況下，dp［i］ ［j］ 和 dp［i-1］ ［j］、dp［i］ ［j-1］、dp［i-1］ ［j-1］ 肯定存在某種關係。因為我們的目標就是，**從規模小的，透過一些操作，推匯出規模大的。對於這道題，我們可以對 word1 進行三種操作
插入一個字元 刪除一個字元 替換一個字元
由於我們是要讓操作的次數最小，所以我們要尋找最佳操作。那麼有如下關係式：
一、如果我們 word1［i］ 與 word2 ［j］ 相等，這個時候不需要進行任何操作，顯然有 dp［i］ ［j］ = dp［i-1］ ［j-1］。（別忘了 dp［i］ ［j］ 的含義哈）。
二、如果我們 word1［i］ 與 word2 ［j］ 不相等，這個時候我們就必須進行調整，而調整的操作有 3 種，我們要選擇一種。三種操作對應的關係試如下（注意字串與字元的區別）：
（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；
那麼我們應該選擇一種操作，使得 dp［i］ ［j］ 的值最小，顯然有
dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1;
於是，我們的關係式就推出來了，
步驟三、找出初始值
顯然，當 dp［i］ ［j］ 中，如果 i 或者 j 有一個為 0，那麼還能使用關係式嗎？答是不能的，因為這個時候把 i - 1 或者 j - 1，就變成負數了，陣列就會出問題了，所以我們的初始值是計算出所有的 dp［0］ ［0…。n］ 和所有的 dp［0…。m］ ［0］。這個還是非常容易計算的，因為當有一個字串的長度為 0 時，轉化為另外一個字串，那就只能一直進行插入或者刪除操作了。
程式碼如下
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 個字元對應下標是 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
］；
}
最後說下，如果你要練習，可以去 leetcode，選擇動態規劃專題，然後連續刷幾十道，保證你以後再也不怕動態規劃了。當然，遇到很難的，咱還是得掛。
Leetcode 動態規劃直達：
https：//
leetcode-cn。com/tag/dyn
amic-programming/
這裡給大家推薦一份刷題筆記，裡面把各種演算法題型以及經驗都總結了，把這份筆記突擊學習一下，很多演算法考察，基本都穩了，給大家看一下目錄
下載連結：
三、如何最佳化？
前兩天寫一篇長達 8000 子的關於
動態規劃
的文章告別動態規劃，連刷40道動規演算法題，我總結了動規的套路
這篇文章更多講解我平時做題的套路，不過由於篇幅過長，舉了 4 個案例之後，沒有講解最佳化，今天這篇文章就來講解下，對動態規劃的最佳化如何下手，並且以前幾天那篇文章的題作為例子直接講最佳化，如果沒看過的建議看一下（不看也行，我會直接給出題目以及沒有最佳化前的程式碼）：告別動態規劃，連刷40道動規演算法題，我總結了動規的套路
四、最佳化核心：畫圖！畫圖！畫圖
沒錯，80% 的動態規劃題都可以畫圖，其中 80% 的題都可以透過畫圖一下子知道怎麼最佳化，當然，DP 也有一些很難的題，想最佳化可沒那麼容易，不過，今天我要講的，是屬於不怎麼難，且最常見，面試筆試最經常考的難度的題。
下面我們直接透過三道題目來講解最佳化，你會發現，這些題，最佳化過後，程式碼只有細微的改變，你只要會一兩道，可以說是會了 80% 的題。
O（n*m） 空間複雜度最佳化成 O（n）
上次那個青蛙跳臺階的 dp 題是可以把空間複雜度 O（ n） 最佳化成 O（1），本來打算從這道題講起的，但想了下，想要學習 dp 最佳化的感覺至少都是
小小大佬
了，所以就不講了，就從二維陣列的 dp 講起。
案例1：最多路徑數
問題描述
一個機器人位於一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。
問總共有多少條不同的路徑？
這是 leetcode 的 62 號題：
https：//
leetcode-cn。com/problem
s/unique-paths/
這道題的 dp 轉移公式是 dp［i］ ［j］ = dp［i-1］ ［j］ + dp［i］ ［j-1］，程式碼如下
不懂的看我之前文章：告別動態規劃，連刷40道動規演算法題，我總結了動規的套路
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
；
}
// 推匯出 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
］；
}
這種做法的空間複雜度是 O（n * m），下面我們來講解如何最佳化成 O（n）。
dp［i］ ［j］ 是一個二維矩陣，我們來畫個二維矩陣的圖，對矩陣進行初始化
然後根據公式 dp［i］［j］ = dp［i-1］［j］ + dp［i］［j-1］ 來填充矩陣的其他值。下面我們先填充第二行的值。
大家想一個問題，
當我們要填充第三行的值的時候，我們需要用到第一行的值嗎？
答是不需要的，不行你試試，當你要填充第三，第四。。。。第 n 行的時候，第一行的值永遠不會用到，只要填充第二行的值時會用到。
根據公式 dp［i］［j］ = dp［i-1］［j］ + dp［i］［j-1］，我們可以知道，當我們要計算第 i 行的值時，
除了會用到第 i - 1 行外，其他第 1 至 第 i-2 行的值我們都是不需要用到的
，也就是說，對於那部分用不到的值我們還有必要儲存他們嗎？
答是沒必要，我們只需要用一個一維的 dp［］ 來儲存
一行
的歷史記錄就可以了。然後在計算機的過程中，不斷著更新 dp［］ 的值。單說估計你可能不好理解，下面我就手把手來演示下這個過程。
1、剛開始初始化第一行，此時 dp［0。。n-1］ 的值就是第一行的值。
2、接著我們來一邊填充第二行的值一邊更新 dp［i］ 的值，一邊把第一行的值拋棄掉。
為了方便描述，下面我們用arr （i，j）表示矩陣中第 i 行 第 j 列的值。從 0 開始哈，就是說有第 0 行。
（1）、顯然，矩陣（1， 0） 的值相當於以往的初始化值，為 1。然後這個時候矩陣 （0，0）的值不在需要儲存了，因為再也用不到了。
這個時候，我們也要跟著更新 dp［0］ 的值了，剛開始 dp［0］ = （0， 0），現在更新為 dp［0］ = （1， 0）。
（2）、接著繼續更新 （1， 1） 的值，根據之前的公式 （i， j） = （i-1， j） + （i， j- 1）。即 （1，1）=（0，1）+（1，0）=2。
大家看圖，以往的二維的時候， dp［i］［j］ = dp［i-1］ ［j］+ dp［i］［j-1］。現在轉化成一維，不就是
dp[i] = dp[i] + dp[i-1]
嗎？
即 dp［1］ = dp［1］ + dp［0］，而且還動態幫我們更新了 dp［1］ 的值。因為剛開始 dp［i］ 的儲存第一行的值的，現在更新為儲存第二行的值。
（3）、同樣的道理，按照這樣的模式一直來計算第二行的值，順便把第一行的值拋棄掉，結果如下
此時，dp［i］ 將完全儲存著第二行的值，並且我們可以推匯出公式
dp［i］ = dp［i-1］ + dp［i］
dp［i-1］ 相當於之前的 dp［i-1］［j］，dp［i］ 相當於之前的 dp［i］［j-1］。
於是按照這個公式不停著填充到最後一行，結果如下：
最後 dp［n-1］ 就是我們要求的結果了。所以最佳化之後，程式碼如下：
public
static
int
uniquePaths
（
int
m
，
int
n
）
{
if
（
m
<=
0
||
n
<=
0
）
{
return
0
；
}
int
［］
dp
=
new
int
［
n
］；
//
// 初始化
for
（
int
i
=
0
；
i
<
n
；
i
++）{
dp
［
i
］
=
1
；
}
// 公式：dp［i］ = dp［i-1］ + dp［i］
for
（
int
i
=
1
；
i
<
m
；
i
++）
{
// 第 i 行第 0 列的初始值
dp
［
0
］
=
1
；
for
（
int
j
=
1
；
j
<
n
；
j
++）
{
dp
［
j
］
=
dp
［
j
-
1
］
+
dp
［
j
］；
}
}
return
dp
［
n
-
1
］；
}
案例2：編輯距離
接著我們來看昨天的另外一道題，就是
編輯矩陣
，這道題的最佳化和這一道有一點點的不同，上面這道 dp［i］［j］ 依賴於 dp［i-1］［j］ 和 dp［i］［j-1］。而還有一種情況就是 dp［i］［j］ 依賴於 dp［i-1］［j］，dp［i-1］［j-1］ 和 dp［i］［j-1］。
問題描述
給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少運算元 。
你可以對一個
單詞
進行如下三種操作：
插入一個字元 刪除一個字元 替換一個字元
示例
：
輸入：
word1
=
“horse”
，
word2
=
“ros”
輸出：
3
解釋：
horse
->
rorse
（
將
‘h’
替換為
‘r’
）
rorse
->
rose
（
刪除
‘r’
）
rose
->
ros
（
刪除
‘e’
）
解答
昨天的程式碼如下所示，不懂的記得看之前的文章哈：告別動態規劃，連刷40道動規演算法題，我總結了動規的套路
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 個字元對應下標是 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
］；
}
沒有最佳化之間的空間
複雜度
為 O（n*m）
大家可以自己動手做下，按照上面的那個模式，你會最佳化嗎？
對於這道題其實也是一樣的，如果要計算 第 i 行的值，我們最多隻依賴第 i-1 行的值，不需要用到第 i-2 行及其以前的值，所以一樣可以採用一維 dp 來處理的。
不過這個時候要注意，在上面的例子中，我們每次更新完 （i， j） 的值之後，就會把 （i， j-1） 的值拋棄，也就是說之前是一邊更新 dp［i］ 的值，一邊把 dp［i］ 的舊值拋棄的，不過在這道題中則不可以，因為我們還需要用到它。
哎呀，直接舉例子看圖吧，文字繞來繞去估計會繞暈你們。當我們要計算圖中 （i，j） 的值的時候，在案例1 中，我們值需要用到 （i-1， j） 和 （i， j-1）。（看圖中
方格
的顏色）
不過這道題中，我們還需要用到 （i-1， j-1） 這個值（但是這個值在以往的案例1 中，它會被拋棄掉）
所以呢，對於這道題，我們還需要一個額外的變數 pre 來時刻儲存 (i-1,j-1) 的值
。推導公式就可以從二維的
dp［i］［j］ = min（dp［i-1］［j］ ， dp［i-1］［j-1］ ， dp［i］［j-1］） + 1
轉化為一維的
dp［i］ = min（dp［i-1］， pre， dp［i］） + 1。
所以呢，案例2 其實和案例1 差別不大，就是多了個變數來臨時儲存。最終程式碼如下（但是初學者話，程式碼也沒那麼好寫）
程式碼如下
public
int
minDistance
（
String
word1
，
String
word2
）
{
int
n1
=
word1
。
length
（）；
int
n2
=
word2
。
length
（）；
int
［］
dp
=
new
int
［
n2
+
1
］；
// dp［0。。。n2］的初始值
for
（
int
j
=
0
；
j
<=
n2
；
j
++）
dp
［
j
］
=
j
；
// dp［j］ = min（dp［j-1］， pre， dp［j］） + 1
for
（
int
i
=
1
；
i
<=
n1
；
i
++）
{
int
temp
=
dp
［
0
］；
// 相當於初始化
dp
［
0
］
=
i
；
for
（
int
j
=
1
；
j
<=
n2
；
j
++）
{
// pre 相當於之前的 dp［i-1］［j-1］
int
pre
=
temp
；
temp
=
dp
［
j
］；
// 如果 word1［i］ 與 word2［j］ 相等。第 i 個字元對應下標是 i-1
if
（
word1
。
charAt
（
i
-
1
）
==
word2
。
charAt
（
j
-
1
））{
dp
［
j
］
=
pre
；
}
else
{
dp
［
j
］
=
Math
。
min
（
Math
。
min
（
dp
［
j
-
1
］，
pre
），
dp
［
j
］）
+
1
；
}
// 儲存要被拋棄的值
}
}
return
dp
［
n2
］；
}
總結
上面的這些題，基本都是不怎麼難的入門題，除了最後一道相對難一點。並且基本 80% 的二維矩陣 dp 都可以像上面的方法一樣最佳化成 一維矩陣的 dp，核心就是要畫圖，看他們的
值依賴
，當然，還有很多其他比較難的最佳化，但是，我遇到的題中，大部分都是我上面這種型別的最佳化。後面如何遇到其他的，我會作為案例來講，今天就先講
最普遍最通用的最佳化方案
。記住，畫二維 dp 的矩陣圖，然後看元素之間的值依賴，然後就可以很清晰著知道該如何優化了。
在之後的文章中，我也會按照這個步驟，在給大家講四五道動態規劃
hard
級別的題，會放在每天推文的第二條給大家學習。如果覺得有收穫，不放
三連
走起來（點贊、感謝、分享），嘻嘻。
最後，面試大廠，演算法是必不可少的一個環節，給大家推薦一份大佬的刷題筆記，裡面包含了90%的 leetcode 題解，並且都是
最優解
：
如果覺得有幫助，記得三連走起，感謝大家
--------------------2021.6.14更新-------------
遞迴專題搞好了，歡迎大家來學習，接下來就搞動態規劃訓練題
----------------------2021.7.3更新-------------------
答應其他小夥伴，把動態規劃訓練題也更新好了
————————————2021。7。4更新——————————-
帥地已經把練習題補上，並且把遞迴和動態規劃整理成了手冊，送給大家！！！！！只求給我個贊哦
------------------------2021.9.25更新---------------------
帥地建立了一個專注於服務
在校生，校招，面試
的圈子，手把手帶你們學習，歡迎大家的加入，詳情可以看我這篇文章：