本系列文章【資料結構與演算法】所有完整代碼已上傳 github，想要完整代碼的小伙伴可以直接去那獲取，可以的話歡迎點個Star哦~下面放上跳轉鏈接
- https://github.com/Lpyexplore/structureAndAlgorithm-JS
我們在面對很多問題時，會通過遞回去解決問題，雖然遞回的代碼寫起來非常的簡潔，但效率不高，無法高效地將遞回的代碼轉化成機器代碼，
遞回的思想是通過從問題的頂部開始，不斷解決其中的小問題，使得問題得以解決 ；而我們本文要講的動態規劃的思想正好和遞回的思想相反，其主要思想是先從一個個小問題開始解決，直到所有小問題都解決了，整個問題就得以解答，
那么就通過動態規劃的的三個使用案例來體會動態規劃的思想吧
- 公眾號：前端印象
- 不定時有送書活動，記得關注~
- 關注后回復對應文字領取：【面試題】、【前端必看電子書】、【資料結構與演算法完整代碼】、【前端技術交流群】
高級演算法——動態規劃
- 一、什么是動態規劃
- 二、案例一：斐波那契數列
- 三、案例二：尋找最大公共子串
- 四、案例三：背包問題
- 五、結束語
一、什么是動態規劃
文章開頭說到，動態規劃是通過解決一個個小問題從而解決整個大問題的，因此我們一般會創建一個陣列或表來記錄每一個小問題的解決程序，那么我們就能很清楚的看到整個問題的解決程序，
創建一個表其實就是通過陣列嵌套陣列的方式來實作的，假如我們需要一個下圖所示的表
我們只需要通過陣列內嵌套陣列即可
[
[true, true, false, true],
[false, false, true, true],
[true, false, false, false],
[false, false, false, true]
]
我們下面的三個案例也會反復用到這樣的表，所以一定要理解
二、案例一：斐波那契數列
斐波那契數列是遞回中最經典的一個例子，并且代碼寫起來也極其得簡潔
function fibonacci1(n) {
if(n == 1 || n == 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2)
}
看似簡潔的代碼，其實內部有很多不足之處，我們可以用樹結構來分析一下遞回的程序，假設我們要獲取斐波那契數列中第6個數，則遞回程序如下圖所示
很明顯得看到，遞回程序中，有很多值重復求了不止一次，例如 4 和 3 ，若我們要獲取得數比6還大的話，重復求值的現象會更加的明顯，這無疑是很消耗性能的，因此我們可以通過動態規劃的方式來消除這種現象，
假設我們要獲取斐波那契數列第n個數的值，首先我們可以創建個陣列，從第一個數開始，在該陣列中記錄每個索引位置上的值
function fibonacci2(n) {
// 記錄斐波那契數列 第1個數 到 第n個數 的所有值
let arr = [1, 1]
// 獲取n個數之前所有的值，并存盤在arr中
for(let i = 2; i < n; i++) {
arr[i] = arr[i - 1] + arr[i - 2]
}
// 直接從arr中回傳我們要的值
return arr[n - 1]
}
這種方法就是一個最簡單的動態規劃，即通過陣列的形式記錄著求取斐波那契數列這個大問題程序中每一個小問題的值，最后可以直接通過陣列獲取到我們想要的值，
因為其沒有重復求值的缺點，因此效率肯定比遞回的效率高，我們可以來驗證一下
// 遞回求取的開始時間
let start1 = Date.now()
// 遞回求取第40個數的值
console.log(fibonacci1(40))
// 遞回求取的結束時間
let end1 = Date.now()
// 動態規劃求值的開始時間
let start2 = Date.now()
// 動態規劃求取第40個數的值
console.log(fibonacci2(40));
// 動態規劃求值的結束時間
let end2 = Date.now()
console.log(`
遞回所用時間：${end1 - start1} ms
動態規劃所用時間：${end2 - start2} ms
`);
/*
102334155
102334155
遞回所用時間：2476 ms
動態規劃所用時間：0 ms
*/
從結果我們能很明顯地看到，僅僅第40個值對于動態規劃來說根本不算什么，使用的時間幾乎為0，而遞回卻因重復求值使用了2s以上的時間
三、案例二：尋找最大公共子串
首先先來看看問題需求：這里有兩個字串，即 raven 和 havoc，現在我們要封裝一個函式，來獲取這兩個字串的所有最大公共子串，結果就是最大的公共子串為 av，并且最大的公共子串長度為2
首先看到這個問題，我覺得一般大家想到的辦法都是跟圖示一樣
但這是一種簡單粗暴的方法，把它用代碼實作的話，中間也會有很多的重復比較的部分，所以我們這里也可以通過動態規劃來解決此辦法，即創建一個表，用來記錄第一個字串的每一個字符跟第二個字串每一個字符的比較結果，最后再通過觀察表來判斷最大公共子串和最大公共子串的長度
假設現在有這樣兩個字串：abaccd 和 badacef，我們要求它倆的最大公共子串
可以先建一個 8 * 7 的表，如圖所示
行的表頭表示的是第一個字串的第n個字符；列的表頭表示的是第二個字串第m個字符
因此行的表頭或列的表頭為0對應的格子應當都為0，因為字串沒有第0個字符，最少是從第1個開始的，結果如下：
我們先找到行表頭為1的這一行從左往右看，表示拿第一個字串的第一個字符與第二個字串的每一個字符進行比較，若不相同，則在對應格子里填0，表示的是連續相同字符的長度為0；若相同，則先看看該格子的左上角那個格子里的數 n 是多少，然后在該格子里填 n + 1
為什么當相同時要在該格子中填入比左上角的值大1的數呢？因為左上角的格子表示的是第一個字串當前字符的前一個字符與第二個字串當前字符的前一個字符比較后的連續相同字符長度
我們來看一下第一行的填寫程序：
第二行表示的是拿第一個字串的第二個字符與第二個字串的每個字符的比較，程序如圖所示：
第三行表示的是拿第一個字串的第三個字符與第二個字串的每個字符的比較，程序如圖所示：
在上圖第三行的填寫程序中，第一個字串的第三個字符與第二個字串的第二個字符比較相同時，我們查看了一下該格子左上角的值，即判斷了第一個字符當前字符的前一個字符與第二個字符當前字符的前一個字符比較后的連續字符長度為多少
剩下的三行填寫程序如下圖所示：
最終的表格如下圖所示：
從表中我們可以看到，最大的公共子串長度為2，一共有兩個長度為2的公共子串，分別是第一個字串的第2個字符到第3個字符和第一個字串的第3個字符到第4個字符，即 ba 和 ac
根據上面的方法，我們來用代碼封裝一下求取最大公共子串的函式
function publicStr(s1, s2) {
// 創建一個表
let table = []
// 記錄最大的公共子串長度
let max = 0
// 子串進行比較，將表填完整
for(let i = 0; i <= s1.length; i++) {
table[i] = []
for(let j = 0; j <= s2.length; j++) {
// 若行表頭或串列頭為0，格子里填0
if(i == 0 || j == 0) table[i][j] = 0;
// 若字符比對不相同
else if(s1[i - 1] !== s2[j - 1]) table[i][j] = 0;
// 字符比對相同
else {
// 當前格子的值等于左上角格子的值+1
table[i][j] = table[i - 1][j - 1] + 1
// 判斷max是否為最大公共子串的長度
if(table[i][j] > max) max = table[i][j]
}
}
}
// 記錄所有的最大公共子串的資訊
let items = []
// 遍歷整個表，找到所有子串長度為max的子串的最后一個字符的索引
for(let i = 0; i < s1.length; i ++) {
let current = table[i]
for(let j = 0; j < s2.length; j ++) {
if(current[j] === max) items.push(i)
}
}
console.log(`最大子串長度為${max}`);
console.log(`長度為${max}的子串有：`);
for(let i in items) {
let start = items[i] - max
console.log(`${s1.slice(start, start + max)}`);
}
}
我們用上述例子來驗證一下該函式是否正確，同時我還列印了一下表的結果，大家可以跟實體中的比對一下是否正確
let s1 = 'abaccd'
let s2 = 'badacef'
publicStr(s1, s2)
/* 列印結果：
最大公共子串長度為2
長度為2的子串有：
ba
ac
表：[
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]
]
*/
四、案例三：背包問題
背包問題也算是一個非常經典的問題，假設現在你的面前有4種珠寶，它們的重量分別為 3 、3 、4 、5 ，它們的價值分別為 4 、6 、7 、9，現在你有一個能裝下重量為 8 的物品，請問你會如何挑選才能使利益最大化？
當然最簡單的辦法就是寫出所有的組合，然后計算每種組合的價值，然后就能獲得利益最大化的方案
這用遞回實作是非常簡單的，代碼如下
// 封裝一個判斷大小的函式
function max(v1, v2) {
return v1 > v2 ? v1 : v2
}
// 主函式，用于判斷當前背包容量下，存放某個物品的最大收益
// 引數：背包容量、存放每個物品重量的陣列、存放每個物品價值的陣列、物品標號
function knapsack(capacity, size, value, n) {
// 如果沒有物品了或者背包沒容量了，則最大收益為0
if(n == 0 || capacity == 0) return 0;
// 物品n的重量大于背包容量
else if(size[n - 1] > capacity) {
// 回傳上一個物品的最大收益
return knapsack(capacity, size, value, n - 1)
}
// 物品n的重量小于背包容量
else {
// 此時有兩種選擇：第一種：拿該物品 ; 第二種：不拿該物品
// 我們要取其中收益最大的方案，因此用到max函式
return max(value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1))
}
}
// 代碼測驗
let capacity = 8
let size = [3, 3, 4, 5]
let value = [4, 6, 7, 9]
let n = 4
let res = knapsack(capacity, size, value, n)
console.log(res) // 15 , 表示最大收益價值為15
正如我們文章開頭所說的，這樣的遞回效率總歸是不太高的，因此我們要將其用動態規劃實作，并且我們將需求改變一下，不光要求出最大收益價值，還要知道是拿了哪幾樣物品，
同樣的，我們先創建一個表，用來記錄每一種物品在任一背包容量下的最大收益
很明顯，當背包容量為0時，我們能獲得的最大收益一定為0；表中物品編號為0的這一行全部都要填上0，因為這是我們添加的對照行，并沒有編號為0的物品，因此結果如圖所示：
現在我們從編號為1的物品開始，判斷其在背包容量為 1 ~ 8 的情況下，我們能獲取到的最大利益為多少，顯而易見，物品1的重量為3，因此當背包容量小于3時，最大收益都為0；當背包容量大于等于3時，因為還沒有考慮別的物品，因此我們能獲取的最大收益就等于物品1的價值，即等于4，結果如圖所示：
接著我們考慮編號為2的物品在背包容量為 1 ~ 8 的情況下，我們能獲取到的最大利益為多少，
首先知道物品2的重量為3，因此在背包容量小于3時，我們無法放入物品2，那么此時的最大收益就等于在當前背包容量下，放入物品1的最大收益；
當背包容量大于等于3時，我們能放入物品2，因此我們現在有兩種選擇：第一種就是不放物品2，那么我們就只能放物品1，所以我們能獲得的最大收益就等于在此背包容量下放入物品1的最大收益；第二種就是放物品2，因為我們已經放了物品2了，只剩一個物品1了，所以此時的最大收益就等于物品2的價值 + 背包剩余容量下放入物品1的最大收益，我們要取這兩種情況中收益最大的方案
填表程序如下圖所示：
接著我們又考慮編號為3的物品在背包容量為 1 ~ 8 的情況下，我們能獲取到的最大利益為多少，
首先知道物品3的重量為4，因此在背包容量小于4時，我們無法放入物品3，那么我們還需要考慮的就有物品1和物品2，從上一步驟得知，物品2的最大收益時在考慮了物品1的基礎上得出的，因此我們只需要考慮放入物品2的最大收益即可，那么此時的最大收益就等于在當前背包容量下，放入物品2的最大收益；
當背包容量大于等于4時，我們能放入物品4，與上一個步驟類似，我們有兩種選擇，即放物品3和不放物品3
填表結果如下圖所示：
同理，最后一行的填表程序如下圖所示：
最終的填表結果如下圖所示：
在表中可以很明顯地看到，我們在背包容量為8的情況下，能獲取到的最大收益為15
此時，我們還需要倒著推回去，判斷一下是拿了哪幾樣物品才獲取到的最大收益
首先找到最大收益對應的格子為物品4，然后我們判斷一下該收益是否等于前一種物品（物品3）的最大收益，若等于，則表示沒有放入物品4；否則表示放入了物品4，
為什么會這樣判斷呢？因為我們說過，在判斷一個物品在某背包容量下的最大收益時，當物品重量大于背包容量或者我們選擇不放入該物品時，此時的最大收益就等于前一種物品在此背包容量下的最大收益
所以這里能判斷，我們放入了物品4，則此時背包容量只剩 8 - 5 = 3，所以我們找到物品3在背包容量等于3情況下最大收益對應的格子，同樣判斷一下上一種物品（物品2）的最大收益是否等于此格子中的最大收益，當前判斷為相等，因此我們沒有放入物品3
當前背包容量仍為3，我們找到物品2在背包容量等于3情況下最大收益對應的格子，判斷當前最大收益不等于上一種物品（物品1）在背包容量為3情況下的最大收益，因此我們放入了物品2
則此時背包容量為 3 - 3 = 0了，無法再放入任何物品了，所以我們就可以得出結論，我們在放入物品2和物品4的情況下收益最大，最大收益價值為15
上面講解了背包問題的動態規劃思路，下面我們用代碼來實作一下
function knapsack(capacity, size, value, n) {
// 回傳較大的值
function max(v1, v2) {
return v1 > v2 ? v1 : v2
}
let table = []
// 生成長度為n的表
for(let i = 0; i <= n; i++) {
table[i] = []
}
// 判斷每種物品面對不同背包容量時的最大收益
for(let i = 0; i <= n; i++) {
for(let j = 0; j <= capacity; j++) {
// 物品種類序列為0或者背包容量為0時，最大收益為0
if(i == 0 || j == 0) table[i][j] = 0;
// 背包容量小于物品重量時，最大收益等于上一種物品在此背包容量下的最大收益
else if(size[i - 1] > j) {
table[i][j] = table[i - 1][j]
}
/* 背包容量大于物品重量時，最大收益分兩種情況：
第一種情況：不放此物品，則最大收益等于上一種物品在此背包容量下的最大收益；
第二種情況：放此物品，則最大收益等于該物品的收益加上剩余背包容量下，上一種物品的最大收益
*/
else {
table[i][j] = max(table[i - 1][j], value[i - 1] + table[i - 1][j - size[i - 1]])
}
}
}
// 最大收益值
let max_value = 0
let which = -1
// 尋找在背包容量為capacity時的最大收益值，以及最大收益值所對應的物品種類
for(let i in table) {
let k = table[i][capacity]
if(k > max_value) {
max_value = k
which = i
}
}
// 記錄所裝的物品
let goods = []
// 記錄背包剩余容量
let rest = capacity
while(rest > 0 && which > 0) {
// 若此時的最大收益不等于上一種物品在此背包容量下的最大收益，則放了此物品；否則就沒放此物品
if(table[which][rest] !== table[which - 1][rest]) {
goods.push(which)
rest -= size[which - 1]
}
which --
}
console.log(`背包最大的收益為：${max_value}，拿取的物品有${goods.join(',')}`);
}
我們通過上面舉得例子來驗證一下封裝好的函式的正確性，為了方便大家進行驗證，我同時列印了代碼中的表，可以和前面例子中最終填完的表進行比對
let size = [3, 3, 4, 5]
let value = [4, 6, 7, 9]
let capacity = 8
let n = 4
knapsack(capacity, size, value, n)
/* 列印結果：
背包最大的收益為：15，拿取的物品有4,2
表：[
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 4, 4, 4, 4, 4, 4],
[0, 0, 0, 6, 6, 6, 10, 10, 10],
[0, 0, 0, 6, 7, 7, 10, 13, 13],
[0, 0, 0, 6, 7, 9, 10, 13, 15]
]
*/
可以看到，利用動態規劃的方式解決背包問題，我們能清晰地看到整個問題地解決程序，還可以通過回溯的方式知道是放入了哪些物品獲得的最大收益
五、結束語
高級演算法中的動態規劃應用就講到這里吧，【資料結構與演算法】這個專欄最后還只剩一篇文章了，即貪心演算法，我會在之后發出來，也希望大家持續關注，多多支持~
大家可以關注我，之后我還會一直更新別的資料結構與演算法的文章來供大家學習，并且我會把這些文章放到【資料結構與演算法】這個專欄里，供大家學習使用，
然后大家可以關注一下我的微信公眾號：前端印象，等這個專欄的文章完結以后，我會把每種資料結構和演算法的筆記放到公眾號上，大家可以去那獲取，
或者也可以去我的github上獲取完整代碼，歡迎大家點個Star
- https://github.com/Lpyexplore/structureAndAlgorithm-JS
我是Lpyexplore，一個因Python爬蟲而進入前端的探索者，創作不易，喜歡的加個關注，點個收藏，給個贊~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/174804.html
標籤：java