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