文章目录
- 爬楼梯
- 买票股票
- 最大连续子数和
- 0-1背包问题
- 最长公共子序列
爬楼梯
function climbStairs(n){if(n<=1){return 1};let dep = [];dep[0]=1;dep[1]=1;for(let i=2;i<=n;i++){dep[i] = dep[i-1]+dep[i-2]}return dep[n];
}
console.log(climbStairs(5))
买票股票
function maxProfit(prices) {if (prices.length === 0) {return 0;}let minPrice = prices[0];let maxProfit = 0;for (let i = 1; i < prices.length; i++) {minPrice = Math.min(minPrice, prices[i]);maxProfit = Math.max(maxProfit, prices[i] - minPrice);}return maxProfit;}// 示例用法const prices = [7, 1, 5, 3, 6, 4];console.log(maxProfit(prices)); // 输出: 5 (在第2天买入，第5天卖出)
最大连续子数和
function maxSubArray(nums) {let maxSoFar = nums[0];let maxEndingHere = nums[0];// maxSoFar 用于存储目前为止发现的最大子数组和// maxEndingHere 用于存储以当前元素结尾的最大子数组和let start = 0;let end=0;for (let i = 1; i < nums.length; i++) {let newMaxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);if(maxSoFar<newMaxEndingHere){maxSoFar = newMaxEndingHere;// maxSoFar 改变了才会改变需要截取的数组if(nums[i]>maxEndingHere + nums[i]){start = i;end = i;}else if(nums[i]<maxEndingHere + nums[i]){end = i;}}maxEndingHere = newMaxEndingHeremaxSoFar = Math.max(maxSoFar, maxEndingHere);}let childArr = nums.slice(start,end+1)return {maxSoFar,childArr};
}
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) //[4,-1,2,1] 60-1背包问题
对于每个物品 i 和每个容量 j，我们有两种选择：
- 不放入物品 i：此时最大价值就是前 i-1 个物品放入容量为 j 的背包中的最大价值，即 dp[i-1][j]。
- 放入物品 i：如果物品 i 的重量 w[i] 小于等于当前背包容量 j，我们可以选择放入物品 i。此时，背包的剩余容量变为 j - w[i]，我们需要从前 i-1 个物品中选择一些放入剩余容量的背包中，以获得最大价值。这个最大价值是 dp[i-1][j-w[i]]。再加上物品 i 的价值 v[i]，总价值就是 dp[i-1][j-w[i]] + v[i]。
综上所述，我们可以得到状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
function knapsack(weights, values, maxWeight) {const n = weights.length;const dp = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(0));// 动态规划填表for (let i = 1; i <= n; i++) {for (let w = 1; w <= maxWeight; w++) {if (weights[i - 1] <= w) {// 如果当前物品可以放入背包dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);console.log(dp[i - 1][w],'----', dp[i - 1][w - weights[i - 1]] ,values[i - 1])} else {// 如果当前物品不能放入背包dp[i][w] = dp[i - 1][w];}}}// dp[n][maxWeight] 存储了最大价值return dp[n][maxWeight];}// 示例const weights = [2, 3, 4, 5];const values = [3, 4, 5, 6];const maxWeight = 5;console.log(knapsack(weights, values, maxWeight)); // 输出：7
最长公共子序列
动态规划解决最长公共子序列（Longest Common Subsequence, LCS）问题的步骤如下：
-
定义状态：定义一个二维数组
dp[i][j]，其中dp[i][j]表示字符串X的前i个字符和字符串Y的前j个字符的最长公共子序列的长度。 -
初始化：初始化
dp数组的第一行和第一列为 0，因为一个空字符串与任何字符串的最长公共子序列长度都是 0。 -
状态转移方程
- 如果
X[i-1] == Y[j-1]，则dp[i][j] = dp[i-1][j-1] + 1，表示当前字符可以构成最长公共子序列的一部分。 - 如果
X[i-1] != Y[j-1]，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示忽略当前字符，取上一个字符的最长公共子序列。
-
计算最优值：
dp数组的最后一个元素dp[m][n]即为最长公共子序列的长度。 -
回溯找到子序列：从
dp[m][n]开始，根据状态转移方程反向回溯，构建最长公共子序列。 -
输出结果：输出最长公共子序列的长度和字符序列。
function longestCommonSubsequence(str1, str2) {const m = str1.length;const n = str2.length;// 创建一个 (m+1) x (n+1) 的二维数组 dpconst dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));// 动态规划填表for (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {if (str1[i - 1] === str2[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]);}}}// dp[m][n] 存储了 str1 和 str2 之间的最长公共子序列的长度// return dp[m][n];let lcs = '';let i = m;let j = n;while (i > 0 && j > 0) {if (str1[i - 1] === str2[j - 1]) {lcs = str1[i - 1] + lcs;i--;j--;} else if (dp[i - 1][j] > dp[i][j - 1]) {i--;} else {j--;}}return lcs;
}// 示例
console.log(longestCommonSubsequence("abcde", "ace")); // 输出：3
console.log(longestCommonSubsequence("ABCDEF", "ACDFE")); // 输出：
