我們一起聊聊十五周算法訓練營中的普通動態(tài)規(guī)劃
作者：前端點線面
一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
最長遞增子序列
給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴格遞增子序列的長度。
子序列 是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。
示例 1：
輸入：nums = [10,9,2,5,3,7,101,18] 輸出：4 解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。
// 遞歸的形式試試(這種形式可定不滿足面試官要求，從而超時，但是在這個基礎上可以改成備忘錄，備忘錄之后進而改成動態(tài)規(guī)劃)
function lengthOfLIS1(nums) {
// 該遞歸函數(shù)表示以nums[index]結尾的部分的最長遞增子序列值
const helper = (nums, index) => {
// 邊界條件
if (index === 0) {
return 1;
}
let result = 1;
for (let i = 0; i < index; i++) {
// 獲取子問題結果
const subproblem = helper(nums, i);
// 然后判斷nums[i] 與nums[index]的大小
if (nums[i] < nums[index]) {
result = Math.max(result, subproblem + 1);
}
}
return result;
};
let result = 0;
// 因為最長遞增子序列有可能以任意值結果，所以遍歷一遍找到最大
for (let i = 0; i < nums.length; i++) {
result = Math.max(helper(nums, i), result);
}
return result;
}
// 備忘錄形式進行優(yōu)化
function lengthOfLIS2(nums) {
const map = new Map();
const helper = (nums, index) => {
if (index === 0) {
return 1;
}
if (map.has(index)) {
return map.get(index);
}
let result = 1;
for (let i = 0; i < index; i++) {
const subproblem = helper(nums, i);
if (nums[i] < nums[index]) {
result = Math.max(result, subproblem + 1);
}
}
return result;
};
let result = 1;
for (let i = 0; i < nums.length; i++) {
result = Math.max(result, helper(nums, i));
}
return result;
}
// 設計動態(tài)規(guī)劃算法，需要一個dp數(shù)組，假設dp[0……i-1]已經(jīng)被算出來了，然后根據(jù)這些結果算出來dp[i]
// 在該問題中，dp數(shù)組的含義是：dp[i]表示以nums[i]這個數(shù)結尾的最長遞增子序列的長度
// 根據(jù)這個定義可以推出bad case：dp[i]初始值為1，因為以nums[i]結尾的最長遞增子序列起碼要包含它自己
// 如何找到動態(tài)規(guī)劃的狀態(tài)轉移關系
// 1. 明確dp數(shù)組所存數(shù)據(jù)的含義
// 2. 根據(jù)dp數(shù)組的含義，運用數(shù)學歸納法的思想，假設dp[0……i-1]都已知，想辦法求出dp[i],一旦這一步完成，整個題目基本就解決了
function lengthOfLIS3(nums) {
// 初始化dp數(shù)組,dp[i]表示以nums[i]這個數(shù)結尾的最長遞增子序列的長度，其中最小為1
const dp = new Array(nums.length).fill(1);
let result = 0;
// 遍歷一遍
for (let i = 0; i < nums.length; i++) {
// 要找到以i為結尾的最長遞增子序列，就是前面i - 1項中存在的最長遞增子序列 + 1，通過比較獲取其最大的
for (let j = 0; j < i; j++) {
// 當nums[j]的值小于[i]的值時,才滿足遞增子序列的要求
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 獲取從0-n中最長的
result = Math.max(result, dp[i]);
}
return result;
}
const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS1(nums));
console.log(lengthOfLIS2(nums));
console.log(lengthOfLIS3(nums));最長公共子序列
給定兩個字符串 text1 和 text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。
一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。
示例 1：
輸入：text1 = "abcde", text2 = "ace" 輸出：3
解釋：最長公共子序列是 "ace" ，它的長度為 3 。
// 既然是最值問題，肯定優(yōu)先考慮動態(tài)規(guī)劃
// 對于兩個字符串求子序列的問題，都是用兩個指針i和j分別在兩個字符串上移動，大概率是動態(tài)規(guī)劃的思路
// 首先寫一個dp函數(shù)：
// 定義：計算 s1[0……i] 和 s2[0……j] 的最長公共子序列長度
// int dp(String s1, int i, String s2, int j)
// 這個dp函數(shù)的定義是：dp(s1, i, s2, j)計算s1[0……i]和s2[0……j]的最長公共子序列長度。
// 根據(jù)這個定義，那么我們想要的答案就是dp(s1, s1.length, s2, s2.length)，且 base case 就是i < 0或j < 0時，因為這時候s1[0……i]或s2[0……j]就相當于空串了，最長公共子序列的長度顯然是 0
// 如果在求dp[i][j]的時候，此時會出現(xiàn)以下幾種情況：
// 1. 如果text1[i] === text2[j],此時證明該字符在該lcs中，則dp[i][j] = dp[i - 1][j - 1] + 1;
// 2. 如果text1[i] !== text2[j],此時可能：
// （1）text1[i]不在lcs中；
// （2) text2[j]不在lcs中；
// （3）text1[i]和text2[j]都不在lcs中
// 則dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]),注：dp[i - 1][j - 1]可以被省略,因為多一個字符去比較肯定比少一個字符去比較結果長
// 暴力遞歸
function longestCommonSubsequence1(text1, text2) {
const dp = (text1, i, text2, j) => {
// base case
if (i < 0 || j < 0) {
return 0;
}
if(text1[i] === text2[j]) {
return dp(text1, i - 1, text2, j - 1) + 1;
} else {
return Math.max(dp(text1, i - 1, text2, j), dp(text1, i, text2, j - 1), dp(text1, i - 1, text2, j - 1));
}
};
return dp(text1, text1.length - 1, text2, text2.length - 1);
}
// 備忘錄法
function longestCommonSubsequence2(text1, text2) {
// 用一個二維數(shù)組去存儲對應的結果值，在遞歸的時候首先判斷是否存在這樣的結果，有的話直接返回
}
// 改成動態(tài)規(guī)劃的形式
// 首先判斷是否具備最優(yōu)子結構，只有具備最優(yōu)子結構，才能通過子問題得到原問題的最值
// 緊接著找到正確的狀態(tài)轉移方程
// 1. 明確狀態(tài)：本題的狀態(tài)就是text1[0……i]和tex2[0……j]的最長子序列
// 2. 定義dp數(shù)組/函數(shù)：dp[i][j]表示text1[0……i]和tex2[0……j]的最長子序列
// 3. 明確選擇：為了獲取dp[i][j],需要指導dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1]
// 4. 明確base case:此處的base case就是i < 0或j < 0,這個時候一個串為空，最長公共子序列長度就為0
function longestCommonSubsequence3(text1, text2) {
// 定義dp
const dp = new Array(text1.length + 1);
for (let i = 0; i < dp.length; i++) {
// base case
dp[i] = (new Array(text2.length + 1)).fill(0);
}
for (let i = 1; i < dp.length; i++) {
for (let j = 1; j < dp[0].length; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[dp.length - 1][dp[0].length - 1];
}
const text1 = 'abcde';
const text2 = 'ace';
console.log(longestCommonSubsequence1(text1, text2));
console.log(longestCommonSubsequence3(text1, text2));打家劫舍
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
示例 1：
輸入：[1,2,3,1] 輸出：4 解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。
const nums = [1, 2, 3, 1];
// 暴力遞歸方式
function rob1(nums) {
const dp = (nums, start) => {
// 設定遞歸結束條件
if (start >= nums.length) {
return 0;
}
// dp(nums, start + 1)表示不搶，去下一家
// nums[start] + dp(nums, start + 2)表示搶，去下下家
const result = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));
return result;
};
return dp(nums, 0);
}
console.log(rob1(nums));
// 帶備忘錄的遞歸解法
function rob2(nums) {
const map = new Map();
const dp = (nums, start) => {
if (map.has(start)) {
return map.get(start);
}
if (start >= nums.length) {
return 0;
}
const result = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2));
map.set(start, result);
return result;
}
return dp(nums, 0);
}
console.log(rob2(nums));
// 動態(tài)規(guī)劃
function rob3(nums) {
const n = nums.length;
const map = new Map();
// 當超出房間后，搶到的都為0
map
.set(n, 0)
.set(n + 1, 0);
for (let i = n - 1; i >= 0; i--) {
map.set(i, Math.max(map.get(i + 1), nums[i] + map.get(i + 2)));
}
return map.get(0);
}
console.log(rob3(nums));
// 發(fā)現(xiàn)狀態(tài)轉移只和dp[i]最近的兩個狀態(tài)有關，可以進一步優(yōu)化，將空間復雜度由O(N)變?yōu)镺(1)
function rob4(nums) {
const n = nums.length;
let dpi1 = 0;
let dpi2 = 0;
let dpi = 0;
for (let i = n - 1; i >= 0; i--) {
dpi = Math.max(dpi1, dpi2 + nums[i]);
dpi2 = dpi1;
dpi1 = dpi;
}
return dpi;
}
console.log(rob4(nums));
// 該問題是求最值問題，優(yōu)先考慮動態(tài)規(guī)劃
// 動態(tài)規(guī)劃問題首先考慮是否具備最優(yōu)子結構，只有具備最優(yōu)子結構才能夠使用動態(tài)規(guī)劃
// 1. 狀態(tài)和選擇
// 本問題的狀態(tài)：當前房子的索引
// 選擇就是：搶與不搶
// 2. dp數(shù)組含義
// dp[i]表示從i索引開始能夠在不報警前提下?lián)尩降淖疃噱X數(shù)
// 3. 狀態(tài)轉移
// 如果想求得dp[i],則nums[i]搶與不搶得到的最大值,即dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2])
// 4. base case
// 當i === nums.length || i === nums.length + 1時，結果為0
function rob5(nums) {
const dp = (new Array(nums.length + 2)).fill(0);
// 遍歷數(shù)組
for (let i = nums.length - 1; i >= 0; i--) {
dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i]);
}
return dp[0];
}
console.log(rob5(nums));使用最小花費爬樓梯
給你一個整數(shù)數(shù)組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。
你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。
請你計算并返回達到樓梯頂部的最低花費。
示例 1：
輸入：cost = [10,15,20] 輸出：15 解釋：你將從下標為 1 的臺階開始。
- 支付 15 ，向上爬兩個臺階，到達樓梯頂部?？偦ㄙM為 15 。
// 最值問題優(yōu)先考慮動態(tài)規(guī)劃
// 1. 狀態(tài)和選擇
// 狀態(tài)：階數(shù)
// 選擇：跳1臺階或2臺階
// 2. dp數(shù)組函數(shù)
// 達到n臺階所需要的最小費用
// 3. 狀態(tài)轉移邏輯
// dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
// 4. base case
// dp[0] = 0;
// dp[1] = 0;
// dp[2] = Math.min(cost[0], cost[1])
function minCostClimbingStairs(cost) {
const n = cost.length;
const dp = (new Array(n + 1)).fill(0);
// base case
dp[2] = Math.min(cost[0], cost[1]);
// 循環(huán)
for (let i = 3; i < dp.length; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
const cost = [10,15,20];
console.log(minCostClimbingStairs(cost));不同的二叉搜索樹
給你一個整數(shù) n ，求恰由 n 個節(jié)點組成且節(jié)點值從 1 到 n 互不相同的 二叉搜索樹 有多少種？返回滿足題意的二叉搜索樹的種數(shù)。
示例 1：
輸入：n = 3 輸出：5
// 二叉樹問題
// 考慮遍歷一遍二叉樹或遞歸
function numTrees(n) {
// 為了解決子問題重復問題，引入備忘錄
const memo = [];
for (let i = 0; i <= n; i++) {
memo.push([]);
for (let j = 0; j <= n; j++) {
memo[i].push(0);
}
}
// 遞歸獲取結果
const count = (low, high) => {
// 遞歸終止條件
if (low > high) {
return 1;
}
if (memo[low][high] > 0) {
return memo[low][high];
}
let result = 0;
for (let i = low; i <= high; i++) {
result += count(low, i - 1) * count(i + 1, high);
}
memo[low][high] = result;
return result;
};
return count(1, n);
}
console.log(numTrees(3));責任編輯：武曉燕
來源：
前端點線面
