告別動態規劃,連刷 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更新---------------------
帥地建立了一個專注於服務
在校生,校招,面試
的圈子,手把手帶你們學習,歡迎大家的加入,詳情可以看我這篇文章: