十五周算法訓(xùn)練營——普通動態(tài)規(guī)劃（上）
作者：前端點線面
斐波那契數(shù) （通常用 F(n) 表示）形成的序列稱為 斐波那契數(shù)列 。該數(shù)列由 0 和 1 開始，后面的每一項數(shù)字都是前面兩項數(shù)字的和。
今天是十五周算法訓(xùn)練營的第十一周，主要講普通動態(tài)規(guī)劃（上）專題。
斐波那契數(shù)
斐波那契數(shù) （通常用 F(n) 表示）形成的序列稱為 斐波那契數(shù)列 。該數(shù)列由 0 和 1 開始，后面的每一項數(shù)字都是前面兩項數(shù)字的和。也就是：
F(0) = 0，F(xiàn)(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 給定 n ，請計算 F(n) 。
示例 1：
輸入：n = 2 輸出：1 解釋：F(2) = F(1) + F(0) = 1 + 0 = 1
// 1. 暴力遞歸的方法
// 時間復(fù)雜度O(2^n)
function fib1(n) {
if (n === 1 || n === 2) {
return 1;
}
return fib1(n - 1) + fib1(n - 2);
}
const startTime1 = (new Date()).getTime();
console.log(fib1(30));
const endTime1 = (new Date()).getTime();
console.log(endTime1 - startTime1);
// 2. 帶備忘錄的遞歸解法（解決了重復(fù)計算的問題）
// 時間復(fù)雜度O(n)
function fib2(n) {
// 利用Map存儲已經(jīng)求過值的結(jié)果
const map = new Map();
const helper = n => {
// 對于0和1的處理
if (n === 1 || n === 2) {
return 1;
}
// 判斷是否已經(jīng)計算過，計算過則返回該值
if (map.has(n)) {
return map.get(n);
}
// 進行遞歸求值
map.set(n, helper(n - 1) + helper(n - 2));
// 返回求得的值
return map.get(n);
}
return helper(n);
}
const startTime2 = (new Date()).getTime();
console.log(fib1(30));
const endTime2 = (new Date()).getTime();
console.log(endTime2 - startTime2);
// 3. 動態(tài)規(guī)劃
// 在備忘錄啟發(fā)下，可以把備忘錄獨立出來成為一張表（DP table），在該表上完成自底向上的推算
function fib3(n) {
const map = new Map();
map
.set(1, 1)
.set(2, 1);
for (let i = 3; i <= n; i++) {
map.set(i, map.get(i - 1) + map.get(i - 2));
}
return map.get(n);
}
const startTime3 = (new Date()).getTime();
console.log(fib1(30));
const endTime3 = (new Date()).getTime();
console.log(endTime3 - startTime3);
// 4. 在動態(tài)規(guī)劃基礎(chǔ)上進行優(yōu)化，由空間復(fù)雜度從O(n)優(yōu)化到O(1)
function fib4(n) {
if (n === 1 || n === 2) {
return 1;
}
let prev = 1;
let curr = 1;
for (let i = 3; i <= n; i++) {
const sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
const startTime4 = (new Date()).getTime();
console.log(fib1(30));
const endTime4 = (new Date()).getTime();
console.log(endTime4 - startTime4);零錢兌換
給你一個整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個整數(shù) amount ，表示總金額。
計算并返回可以湊成總金額所需的 最少的硬幣個數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。
你可以認(rèn)為每種硬幣的數(shù)量是無限的。
示例 1：
輸入：coins = [1, 2, 5], amount = 11 輸出：3 解釋：11 = 5 + 5 + 1
const coins = [1, 2, 5];
const amount = 19;
// 1. 暴力遞歸，可以找出狀態(tài)轉(zhuǎn)移方程
function coinChange1(coins, amount) {
const dp = function (amount) {
// 邊界條件：當(dāng)目標(biāo)金額為0時結(jié)果為0
if (amount === 0) {
return 0;
}
// 邊界條件：當(dāng)目標(biāo)金額為負(fù)數(shù)時輸出-1
if (amount < 0) {
return -1;
}
// 定義結(jié)果為正無窮
let result = Infinity;
// 進行循環(huán)遍歷
for (let i = 0; i < coins.length; i++) {
// 獲取子問題結(jié)果
const subproblem = dp(amount - coins[i]);
// 如果子問題小于0，則子問題無解，跳出本次循環(huán)
if (subproblem < 0) {
continue;
}
// 獲取較小的結(jié)果
result = Math.min(result, 1 + subproblem);
}
return result === Infinity ? -1 : result;
};
return dp(amount);
}
const startTime1 = (new Date()).getTime();
console.log(coinChange1(coins, amount));
const endTime1 = (new Date()).getTime();
console.log(endTime1 - startTime1);
// 2. 帶備忘錄的遞歸
// 通過備忘錄消除子問題
function coinChange2(coins, amount) {
const map = new Map();
const dp = function (amount) {
if (map.has(amount)) {
return map.get(amount);
}
if (amount < 0) {
return -1;
}
if (amount === 0) {
return 0;
}
let result = Infinity;
for (let i = 0; i < coins.length; i++) {
const subproblem = dp(amount - coins[i]);
if (subproblem < 0) {
continue;
}
result = Math.min(result, 1 + subproblem);
}
map.set(amount, result === Infinity ? -1 : result);
return map.get(amount);
};
return dp(amount);
}
const startTime2 = (new Date()).getTime();
console.log(coinChange2(coins, amount));
const endTime2 = (new Date()).getTime();
console.log(endTime2 - startTime2);
// dp數(shù)組的迭代解法
function coinChange3(coins, amount) {
const map = new Map();
// 設(shè)置邊界條件
map.set(0, 0);
// 每種情況初始化為amount+1,因為最大為amount，amount + 1就相當(dāng)于正無窮
for (let i = 1; i < amount + 1; i++) {
map.set(i, amount + 1);
}
for (let i = 0; i < amount + 1; i++) {
for (let j = 0; j < coins.length; j++) {
if (i - coins[j] < 0) {
continue;
}
map.set(i, Math.min(map.get(i), 1 + map.get(i - coins[j])));
}
}
return map.get(amount) === amount + 1 ? -1 : map.get(amount);
}
const startTime3 = (new Date()).getTime();
console.log(coinChange3(coins, amount));
const endTime3 = (new Date()).getTime();
console.log(endTime3 - startTime3);最小路徑和
給定一個包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。
說明：每次只能向下或者向右移動一步。
示例 1：
輸入：grid = [[1,3,1],[1,5,1],[4,2,1]] 輸出：7 解釋：因為路徑 1→3→1→1→1 的總和最小。
// 該問題是最值問題，優(yōu)先考慮動態(tài)規(guī)劃
// 動態(tài)規(guī)劃問題首先考慮是否具備最優(yōu)子結(jié)構(gòu)，只有具備最優(yōu)子結(jié)構(gòu)才能夠使用動態(tài)規(guī)劃
// 1. 狀態(tài)和選擇
// 本題的狀態(tài)是當(dāng)前在第i行j列
// 選擇就是向下移動或向右移動達到該目標(biāo)位置
// 2. dp數(shù)組含義
// dp[i][j]表示grid[i][j]的最小路徑和
// 3. 狀態(tài)轉(zhuǎn)移邏輯
// 為了得到dp[i][j]需要知道dp[i - 1][j]和dp[i][j - 1]哪個小，從而求得dp[i][j]
// 4. base case
// base case為i === 0 和 j === 0
function minPathSum(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = new Array(m);
for (let i = 0; i < m; i++) {
dp[i] = (new Array(n)).fill(0);
}
// base case
dp[0][0] = grid[0][0];
for (let i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (let j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 遍歷dp
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
console.log(dp);
return dp[m - 1][n - 1];
}
const grid = [
[1,2,3]
,[4,5,6]
];
console.log(minPathSum(grid));石子游戲
Alice 和 Bob 用幾堆石子在做游戲。一共有偶數(shù)堆石子，排成一行；每堆都有 正 整數(shù)顆石子，數(shù)目為 piles[i] 。
游戲以誰手中的石子最多來決出勝負(fù)。石子的 總數(shù) 是 奇數(shù) ，所以沒有平局。
Alice 和 Bob 輪流進行，Alice 先開始 。 每回合，玩家從行的 開始 或 結(jié)束 處取走整堆石頭。 這種情況一直持續(xù)到?jīng)]有更多的石子堆為止，此時手中 石子最多 的玩家 獲勝 。
假設(shè) Alice 和 Bob 都發(fā)揮出最佳水平，當(dāng) Alice 贏得比賽時返回 true ，當(dāng) Bob 贏得比賽時返回 false 。
示例 1：
輸入：piles = [5,3,4,5] 輸出：true 解釋： Alice 先開始，只能拿前 5 顆或后 5 顆石子 。 假設(shè)他取了前 5 顆，這一行就變成了 [3,4,5] 。 如果 Bob 拿走前 3 顆，那么剩下的是 [4,5]，Alice 拿走后 5 顆贏得 10 分。 如果 Bob 拿走后 5 顆，那么剩下的是 [3,4]，Alice 拿走后 4 顆贏得 9 分。 這表明，取前 5 顆石子對 Alice 來說是一個勝利的舉動，所以返回 true 。
- 博弈問題都這么解決
// 該問題用動態(tài)規(guī)劃解決
// 動態(tài)規(guī)劃問題首先考慮是否具備最優(yōu)子結(jié)構(gòu)，只有具備最優(yōu)子結(jié)構(gòu)才能夠使用動態(tài)規(guī)劃
// 1. 狀態(tài)和選擇
// 狀態(tài)：石堆的左索引、右索引、當(dāng)前輪到的人
// 選擇：選擇拿左邊還是右邊
// 2. dp數(shù)組含義
// dp[i][j]表示Alice和Blob的石子個數(shù)分別是多少
// 3. 狀態(tài)轉(zhuǎn)移方程
// 為了得到dp[i][j]需要知道dp[i + 1][j]和dp[i][j - 1],得到最優(yōu)解
// 4. base case
// base case就是i === j時
// 因為計算dp[i][j]時需要知道dp[i+1][j],所以需要倒著進行遍歷數(shù)組
// 注意：在這個過程中，先手做成選擇之后就變成了后手，后手在對方做完選擇后，就變成了先手。這種角色互換使得可以重用之前的結(jié)果，典型的動態(tài)規(guī)劃的標(biāo)志
function stoneGame(piles) {
const n = piles.length;
// dp數(shù)組
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(n);
}
// base case
for (let i = 0; i < n; i++) {
dp[i][i] = [piles[i], 0];
}
// 遍歷dp數(shù)組
for (let i = n - 2; i >= 0; i--) {
for (let j = i + 1; j < n; j++) {
// 先手先選擇左邊或者右邊
// 當(dāng)先手進行選擇后，其在其子問題中就變成了后手
const selectLeft = piles[i] + dp[i + 1][j][1];
const selectRight = piles[j] + dp[i][j - 1][1];
if (selectLeft > selectRight) {
// 如果左側(cè)大于右側(cè)，則先手值就是左側(cè)值，后手值就是其子問題的先手值
dp[i][j] = [selectLeft, dp[i + 1][j][0]];
} else {
dp[i][j] = [selectRight, dp[i][j - 1][0]];
}
}
}
// 結(jié)果存儲在dp[0][n - 1]中
const resultArr = dp[0][n - 1];
return resultArr[0] > resultArr[1];
}
const piles = [5, 3, 4, 5];
console.log(stoneGame(piles));最大子數(shù)組問題
給你一個整數(shù)數(shù)組 nums ，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。
子數(shù)組 是數(shù)組中的一個連續(xù)部分。
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4] 輸出：6 解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。
// 既然是最值問題，肯定優(yōu)先考慮動態(tài)規(guī)劃
// 首先判斷是否具備最優(yōu)子結(jié)構(gòu)，只有具備最優(yōu)子結(jié)構(gòu)，才能通過子問題的最值得到原問題的最值【該問題肯定具備最優(yōu)子結(jié)構(gòu)，因為若求nums[0……i],知道其最優(yōu)子結(jié)構(gòu)nums[0……i - 1】肯定可以求得
// 緊接著就要找正確的狀態(tài)轉(zhuǎn)移方程
// 1. 明確狀態(tài)：本題的狀態(tài)就是nums[0……i]的最大子數(shù)組和
// 2. 定義dp數(shù)組/函數(shù):dp[i]表示nums[0……i]中以i位置結(jié)尾的最大子數(shù)組和
// 3. 明確選擇：為了獲取dp[i]的最大子數(shù)組和，需要指導(dǎo)dp[i - 1]的最大子數(shù)組和
// 4. 明確base case：此處的base case就是dp[0] = nums[0]
function maxSubArray(nums) {
const dp = new Array(nums.length).fill(-Infinity);
// base case
dp[0] = nums[0];
for (let i = 1; i < nums.length; i++) {
dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];
}
return Math.max(...dp);
}
// 注：其實此題還可以進行狀態(tài)壓縮，因為dp[i]只和dp[i - 1]相關(guān)
function maxSubArray1(nums) {
let pre = nums[0];
let maxVal = pre;
for (let i = 1; i < nums.length; i++) {
pre = Math.max(pre + nums[i], nums[i]);
maxVal = Math.max(maxVal, pre);
}
return maxVal;
}
const nums = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubArray(nums));編輯距離
給你兩個單詞 word1 和 word2， 請返回將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。
你可以對一個單詞進行如下三種操作：
插入一個字符 刪除一個字符 替換一個字符
示例 1：
輸入：word1 = "horse", word2 = "ros" 輸出：3 解釋： horse -> rorse (將 'h' 替換為 'r') rorse -> rose (刪除 'r') rose -> ros (刪除 'e')
// 因為是最值問題，優(yōu)先考慮動態(tài)規(guī)劃
// 解決兩個字符串的動態(tài)規(guī)劃問題，一般都是用兩個指針i、j分別指向兩個字符串的最后，然后一步步往前走，縮小問題的規(guī)模
// 方案一：暴力遞歸
function minDistance1(word1, word2) {
const helper = (i, j) => {
// 確定base case，該題目的base case就是當(dāng)i走完s1或j走完s2，然后將對應(yīng)剩下的長度返回
if (i === -1) {
return j + 1;
}
if (j === -1) {
return i + 1;
}
if (word1[i] === word2[j]) {
// 如果兩個字符一樣，則跳過
return helper(--i, --j);
} else {
// 如果兩個字符不一樣，則在插入、刪除、替換中選擇最小的一個返回,然后加上該步驟操作
return Math.min(helper(i, j - 1), helper(i - 1, j), helper(i - 1, j - 1)) + 1;
}
};
return helper(word1.length - 1, word2.length - 1);
}
// 方案二：備忘錄
// 用遞歸暴力解決肯定會存在重疊子問題，所以需要解決重疊子問題
// 通過備忘錄解決子問題就是將[i, j]對應(yīng)的值進行保存，然后運行的時候判斷有沒有
function minDistance2(word1, word2) {
}
// 方案三：動態(tài)規(guī)劃
// 因為是最值問題，優(yōu)先考慮動態(tài)規(guī)劃
// 判斷是否具備最優(yōu)子結(jié)構(gòu)
// 找到正確的狀態(tài)轉(zhuǎn)移方程：
// 1. 明確狀態(tài)，本題中狀態(tài)就是在i位置的字符串到在j位置的字符串的編輯距離
// 2. 定義dp數(shù)組/函數(shù)的含義：本次dp為二維數(shù)組，表示s1[0……i]和s2[0……j]的最小編輯距離
// 3. 明確選擇：為了知道dp[i][j]的值，需要知道dp[i - 1][j - 1]、dp[i][j - 1]、dp[i - 1][j]的值，因為當(dāng)前位置可以修改、插入、刪除操作
// 4. 明確base case:此處的base case就是i或j等于-1時候的值
function minDistance3(word1, word2) {
// 因為當(dāng)為-1的時候才是base case條件，但是數(shù)組中沒有這個索引，所以整體需要擴大1
const dp = new Array(word1.length + 1);
for (let i = 0; i < dp.length; i++) {
dp[i] = (new Array(word2.length + 1)).fill(-1);
}
// 初始化base case
for (let i = 0; i < dp.length; i++) {
dp[i][0] = i;
}
for (let j = 0; j < dp[0].length; j++) {
dp[0][j] = j;
}
// 進行dp數(shù)組的遍歷，在遍歷過程中需要注意：
// 1. 遍歷過程中所需的狀態(tài)必須是已經(jīng)計算出來的；
// 2. 遍歷的終點必須是存儲結(jié)果的那個位置，此處是dp[word1.length][word2.length]
for (let i = 1; i < dp.length; i++) {
for (let j = 1; j < dp[i].length; j++) {
// 因為整體移動了一個位置，所以比較的字符需要減一
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;
}
}
}
// 最終編輯距離就是dp[word1.length][word2.length]
return dp[word1.length][word2.length];
}
const word1 = 'horse';
const word2 = 'ros';
console.log(minDistance1(word1, word2));
console.log(minDistance3(word1, word2));責(zé)任編輯：姜華
來源：
前端點線面
