动态规划
顾名思义，动态添加可选项，每一步规划当前最优解
动态规划适用于每一步都会影响后续的情况,
或者说 每一个状态一定是由上一个状态推导出来, 某一问题有很多重叠子问题,本质是遍历
一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的
- 确定dp数组含义
- 确定递推公式
- 确定dp初始值
- 确定遍历顺序
- 举例推导dp数组
路径问题 背包问题 打家劫舍 股票问题 子序列问题
509. 斐波那契数
https://leetcode.cn/problems/fibonacci-number/
var fib = function(n) {
const dp = [0,1]
for(let i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
};70. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/
var climbStairs = function (n) {
// 1. 确定DP数组含义，下标含义: 达到第i阶有dp[i]种方法
// 2. 确定递推公式: dp[i] = dp[i-2] + dp[i-1]
// 3. dp[0] = 1 (没有0台阶,n为正整数，为了满足规律，赋值个1,其实没用到)
// dp[1] = 1 dp[2] = 2
if (n === 1 || n === 2) return n
const dp = [1, 1, 2]
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1]
}
return dp[n]
};746. 使用最小花费爬楼梯
https://leetcode.cn/problems/min-cost-climbing-stairs/
var minCostClimbingStairs = function(cost) {
// 1. 确定DP数组含义，下标含义: 达到第i阶最少要dp[i]个体力
// 2. 确定递推公式: dp[i] = dp[i-2] + const[i-2] 或
// dp[i] = dp[i-1] + const[i-1] 中的 minor
// 3. 确定初始状态: dp[0] = 0 dp[1] = 0 (可以从0或1开始)
const dp = [0,0]
for(let i = 2; i <= cost.length; i++) {
dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
}
return dp[cost.length]
};
// 优化空间复杂度，因为dp[i]就是由前两位推出来的，那么也不用dp数组了
var minCostClimbingStairs = function(cost) {
let before = after = 0
for(let i = 2; i <= cost.length; i++) {
const now = Math.min(after + cost[i-1], before + cost[i-2])
before = after
after = now
}
return after
};62. 不同路径
https://leetcode.cn/problems/unique-paths/description/
var uniquePaths = function (m, n) {
// dp[i][j] 到达 i j 有多少种走法，抛弃0 0，从 1 1 开始
// dp[i][j] = dp[i-1][j] + dp[i][j-1],要走到ij,必须走到i-1 或 j-1。
// 从[1,1] 走到 [m,n] 需要初始化第一行及第一列为1
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(1))
for (let i = 2; i <= m; i++) {
for (let j = 2; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
return dp[m][n]
};
// 简化到一维，不是很懂
var uniquePaths = function (m, n) {
const dp = new Array(n).fill(1)
for (let j = 1; j < m; j++) {
for (let i = 1; i < n; i++) {
dp[i] += dp[i - 1];
}
}
return dp[n - 1];
};63. 不同路径 II
var uniquePathsWithObstacles = function (obstacleGrid) {
const h = obstacleGrid.length, l = obstacleGrid[0].length
// 初始化时，第一列 或 第一排，假设前面有障碍物，后面都是0
// 先初始化为0，然后赋值1
const dp = new Array(h).fill(0).map(() => new Array(l).fill(0))
for (let i = 0; i < h && obstacleGrid[i][0] === 0; i++) dp[i][0] = 1
for (let i = 0; i < l && obstacleGrid[0][i] === 0; i++) dp[0][i] = 1
for (let i = 1; i < h; i++) {
for (let j = 1; j < l; j++) {
if (obstacleGrid[i][j]) {
dp[i][j] = 0
continue
}
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
return dp[h - 1][l - 1]
};343. 整数拆分
https://leetcode.cn/problems/integer-break/description/
// 首先分析题目，上一步的选择影响当前步，动态规划
var integerBreak = function (n) {
// dp[i] 拆分 i 能得到的最大乘积，i 从 0 到 n
// dp[i] = 遍历到j时，j是必拆。此时存在两种情况
// j * (i - j) 剩余的数不拆； j * dp[i - j] 剩余的数也拆(j*剩余数拆的最大值)
// 最后，dp[i]得是 j 遍历的循环中的最大值，所以 是三者取最大
// dp[0]无意义 dp[1]无意义 均无法拆分 dp[2] = 1，其他得赋值0
let dp = new Array(n + 1).fill(0) // n+1是因为得多算一个0最后才会有dp[n]
dp[2] = 1
for (let i = 3; i <= n; i++) {
// 对于每个i，遍历其 先拆出j能得的最大值，遍历完j后得到当前i能拆出的最大乘积
// 至少拆出两个数，两个数遍历到拆一半的时候肯定是最大的，
// 进一步假设是拆出三个数，那应该遍历到1/3就行，到1/2肯定够
// 所以j <= i / 2
for (let j = 1; j <= i / 2; j++) {
dp[i] = Math.max(j * (i - j), j * dp[i - j], dp[i])
}
}
return dp[n]
};
// 问题来了，什么时候要一重循环，什么时候要二重循环？
// 那就是内部得多遍历一层，内部可能两种情况，三种情况，k种情况
// 这k种情况也依赖上一次的选择，总体有点像动态规划里再动态规划96. 不同的二叉搜索树
https://leetcode.cn/problems/unique-binary-search-trees/description/
——背包问题——
- 是排序问题还是组合问题？(外层循环是物品i还是容量j？)
组合问题不考虑顺序，固定顺序，外层循环为 遍历物品i
排序问题考虑顺序， 外层循环为 遍历容量j
- 是完全背包问题，还是01背包问题?(内层循环是正序还是倒序？)
完全背包物品i数量无限，01背包物品仅存在两种状态
01背包 不重复计算当前 物品i， 内层容量j从后往前循环
完全背包 重复计算当前 物品i， 内层容量j从前往后循环
01背包、完全背包、多重背包、分组背包和混合背包
注意很多 dp[i]的定义 dp[i] i既是value又是weight
416. 分割等和子集(01背包)
https://leetcode.cn/problems/partition-equal-subset-sum/description/
698.划分为k个相等的子集
473.火柴拼正方形
var canPartition = function (nums) {
const l = nums.length
if(nums.length < 2) return false
const sum = nums.reduce((pre, cur) => pre + cur, 0)
if (sum % 2 !== 0) return false
const capacity = sum / 2
// dp[i][j] 代表前i个元素能否组成和为j的结果
// [1, 5, 11, 5]
const dp = new Array(l).fill(0).map(() => new Array(capacity).fill(false))
// 第0项 满足 容量为nums[0]的背包
dp[0][nums[0]] = true
// 一步步扩大可选放入背包的物品范围，每片i轮询可理解为，i-1项中加入此i项能否满足容量j
for (let i = 1; i < l; i++) {
// 该层for循环，相当于遍历出了，前i项，能组合出来哪些容量。
for (let j = 0; j <= capacity; j++) {
// 对每新增的第i项进行容量遍历，判断 第i项 能不能放入 容量j 的背包，
// 1. 如果 nums[i] > 容量j 太大不能放入背包，那容量dp[i][j] 沿用之前 dp[i-1][j]的结果(可能i-1项可以满足 容量j，也算)
// 2. 如果 nums[i] <= 容量j 那就有两种情况，
// 情况1 第i项 放入， 那剩余的空间 j - nums[i]，看看dp[i-1]中是否能恰好填充，即dp[i-1][j - nums[i]]是否为true
// 情况2 第i项 不放入， 那沿用 dp[i-1][j] 的结果(前i-1项能满足和为容量j也行)
// 二者有一个成功即为true
// 在遍历的过程中，已经考虑了背包容量 为 0 到 j 的所有情况
if (nums[i] > j) {
dp[i][j] = dp[i - 1][j]
} else if (nums[i] < j) {
// 也可理解为，i-1项能满足容量j也行，i-1项不能满足容量j的话就把 第i项 放入背包，看看i-1项，能不能满足剩余空间。
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
} else {
dp[i][j] = true
}
}
console.log(i,nums[i],dp[i])
}
// dp[l-1][capacity] 代表 用上nums所有元素(l-1),能否组合出容量capacity
return dp[l - 1][capacity]
};
canPartition([1,5,11,5])// 滚动数组,由于每次的数据只依赖于上一层i-1的数据，所以可以直接在当前一维数组比
var canPartition = function(nums) {
const sum = (nums.reduce((p, v) => p + v));
if (sum & 1) return false;
const dp = Array(sum / 2 + 1).fill(0);
for(let i = 0; i < nums.length; i++) {
// 容量j >= nums[i]代表当前i在这个容量都是有选择的，可放进去的
for(let j = sum / 2; j >= nums[i]; j--) {
// 假设 [1,5,11,5]
// 第一轮就是 1 能放进容量 11，并与0比谁大。一轮下来就是[0,1,1,1,...]
// 第二轮就是 5 能放进容量 11 到 0 的话， value加上 并且剩余质量能否补上，并与1比大
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
if (dp[j] === sum / 2) {
return true;
}
}
}
return dp[sum / 2] === sum / 2;
};
canPartition([1,5,11,5])
0 1 [ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
1 5 [ 0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 6, 6 ]
2 11 [ 0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 6, 11 ]
3 5 [ 0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 10, 11 ]1049. 最后一块石头的重量 II(01背包)
https://leetcode.cn/problems/last-stone-weight-ii/description/
// 前面的选择影响后面的选择，动态规划
var lastStoneWeightII = function (stones) {
// 这题本质是找到尽可能接近 sum/2 的组，也即 背包的 value/容量 最大 为 sum/2。
// dp[j]: 前j项最大价值为dp[j]
// 总容量j 减去当前j的容量，剩余的容量的价值， 加上当前j的价值；与上一次ap[j]比出最大值
// dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
const l = stones.length
if (l < 2) return stones[0]
const sum = stones.reduce((p, c) => p + c)
const maxCapacity = Math.ceil(sum / 2)
const dp = new Array(maxCapacity + 1).fill(0)
for (let i = 0; i < l; i++) {
// 在前几次的遍历中，后面的j基本无意义，因为肯定会被覆盖，后续遍历中i物品变多，更能撑满背包
for (let j = maxCapacity; j >= stones[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
}
// console.log(i,stones[i],dp)
}
return Math.abs(dp[maxCapacity] * 2 - sum)
};
lastStoneWeightII([2,7,4,1,8,1])494. 目标和(01背包,组合)
https://leetcode.cn/problems/target-sum/
const findTargetSumWays = (nums, target) => {
// 本质是 将数组分成两个集合，其中一个集合比另一个集合多result
// 那就是 多的那个集合x = (sum + result) / 2,要想办法把这个集合放满有多少种方法
const sum = nums.reduce((p, c) => p + c);
if (Math.abs(target) > sum) return 0
if ((target + sum) % 2) return 0
// 正数集合，和必须为maxCapacity
const maxCapacity = (target + sum) / 2;
// console.log('sum', sum)
// console.log('maxCapacity', maxCapacity)
let dp = new Array(maxCapacity + 1).fill(0);
dp[0] = 1;
for (let i = 0; i < nums.length; i++) {
// 相当于从前往后遍历i，前几轮遍历相当于看i能满足哪个容量
// 后面的遍历，可以满足的容量更多，直至i = 4，
for (let j = maxCapacity; j >= nums[i]; j--) {
// 每新一轮j的遍历，都在上一轮能达到容量j的基础上 dp[j]，
// + 假设j项已入集合，将剩余空间(j - nums[i]) 补满有多少种次数 dp[j - nums[i]]
dp[j] = dp[j] + dp[j - nums[i]];
}
// console.log(i, nums[i], dp)
}
return dp[maxCapacity];
};
findTargetSumWays([2, 1, 2, 3, 5], 3)
// sum 13
// maxCapacity 8 正数集合和必须为8
// 0 2 [ 1, 0, 1, 0, 0, 0, 0, 0, 0 ]
// 1 1 [ 1, 1, 1, 1, 0, 0, 0, 0, 0 ]
// 2 2 [ 1, 1, 2, 2, 1, 1, 0, 0, 0 ]
// 3 3 [ 1, 1, 2, 3, 2, 3, 2, 1, 1 ]
// 4 5 [ 1, 1, 2, 3, 2, 4, 3, 3, 4 ]474. 一和零
https://leetcode.cn/problems/ones-and-zeroes/description/
// 物品的重量有了两个维度的01背包问题
var findMaxForm = function (strs, m, n) {
// dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0))
// dp[i][j] = Math.max(dp[i][j], dp[i- zeroNum][j- oneNum]+1)
let zero = one = 0
// 老规矩循环物品
// 物品一个维度，物品的重量两个维度，需要三重循环
for (let str of strs) {
for(let c of str) {
if(c==='0')zero++
else one++
}
// 内层其实是滚动数组，滚动数组为了保证每个物品只被添加一次，需要倒叙遍历，这里两个都要倒序遍历
for (let i = m; i >= zero; i--) {
for (let j = n; j >= one; j--) {
// ij不放进去 就继承dp[i][j]， ij放进去就计算剩余的位置放满要多少dp[i - zero][j - one]
dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1)
}
}
}
return dp[m][n]
};为什么滚动数组需要倒叙遍历？
因为滚动数组复用需要i-1轮遍历的结果，
假设从后往前做遍历，我们在做第i轮循环的时候，先计算 容量j 较大的数据，此数据会依赖 i-1 轮的遍历结果
前面还依旧保留者 i-1次遍历的dp数据，以供第i轮使用。
假设从前往后做遍历，可以预见 容量j 较小的dp数据会先被覆盖成为 第i轮的数据，使得 容量j较大的数据无法复用 i-1轮的结果，
或者说这样遍历，导致每轮i种，每个容量j 都基于了新的当前i去计算(视为有无数个i物品，也即完全背包问题)
以01背包的思路 甚至可以认为，这样从前往后遍历，已经不仅仅有i层，而是 i*j 层。因为每个 j-1 其实都已经被覆盖为了第j层的数据
——– 完全背包 ——–
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
01背包和完全背包唯一不同就是体现在遍历顺序上
01背包滚动数组是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历
518. 零钱兑换 II
https://leetcode.cn/problems/coin-change-ii/description/
var change = function (amount, coins) {
// dp[i] 前i项能组成的总金额组合数
const dp = new Array(amount + 1).fill(0)
dp[0] = 1
// 上一轮dp[i]有多少种方法 + 这轮剩余空间有多少种方法
// dp[i] = dp[i] + dp[j-coins[i]]
for (let i = 0; i < coins.length; i++) {
for (let j = coins[i]; j <= amount; j++) {
dp[j] = dp[j] + dp[j - coins[i]]
}
}
return dp[amount]
};——– 排列和组合 ——–
这种遍历顺序中dp[j]里计算的是组合数，因为物品放入的顺序固定，不存在重复计算
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
dp[j] += dp[j - coins[i]];
}
}
// [1,2,5] 5
0 1 [ 1, 1, 1, 1, 1, 1 ]
1 2 [ 1, 1, 2, 2, 3, 3 ]
2 5 [ 1, 1, 2, 2, 3, 4 ]这种遍历顺序中dp[j]里算出来的就是排列数！
dp[j] = dp[j] + dp[j - coins[i]] 的过程就好像先插入当前i，再放置dp[j - coins[i]]的
var change = function (amount, coins) {
const dp = new Array(amount + 1).fill(0)
dp[0] = 1
for (let j = 0; j <= amount; j++) { // 1.遍历背包容量
// 针对每一个容量j，遍历i
for (let i = 0; i < coins.length; i++) { // 2.遍历物品
if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
}
console.log(j,dp)
}
return dp[amount]
};
// [1,2,5] 5
// 0 1 2 3 4 5
0 [ 1, 0, 0, 0, 0, 0 ]
1 [ 1, 1, 0, 0, 0, 0 ]
2 [ 1, 1, 2, 0, 0, 0 ]
3 [ 1, 1, 2, 3, 0, 0 ]
4 [ 1, 1, 2, 3, 5, 0 ]
5 [ 1, 1, 2, 3, 5, 9 ]377. 组合总和 Ⅳ
https://leetcode.cn/problems/combination-sum-iv/description/
var combinationSum4 = function(nums, target) {
// dp[i] 前i项和为i的排列个数
const dp = new Array(target + 1).fill(0)
dp[0] = 1 // 0项组成0有一种方式
// dp[i] = dp[i] + dp[i - nums[i]]
for(let i = 0; i <= target; i++) {
for(let j = 0; j < nums.length; j++) {
if(i >= nums[j]) dp[i] = dp[i] + dp[i - nums[j]]
}
}
return dp[target]
};
// [1,2,3] 4
0 [ 1, 0, 0, 0, 0 ]
1 [ 1, 1, 0, 0, 0 ]
2 [ 1, 1, 2, 0, 0 ]
3 [ 1, 1, 2, 4, 0 ]
4 [ 1, 1, 2, 4, 7 ]70. 爬楼梯(每次任意级台阶)
https://leetcode.cn/problems/climbing-stairs/description/
题目修改为每次可走任意级台阶m
var climbStairs = function(n) {
const dp = new Array(n + 1).fill(0);
const m = 2;
dp[0] = 1;
// 每次走j级台阶存在先后顺序，外层遍历
for(let i = 1; i <= n; i++){
for(let j = 1; j <= m; j++){
if(i >= j) {
dp[i] += dp[i - j];
}
}
}
return dp[n];
};322. 零钱兑换
https://leetcode.cn/problems/coin-change/description/
var coinChange = function (coins, amount) {
// i既是value又是weight,要求weight和为amount
// dp[i] ，组成i需要至少dp[i]个硬币
// 必须初始化为最大的数
const dp = new Array(amount + 1).fill(Number.POSITIVE_INFINITY)
dp[0] = 0
for (let i = 0; i < coins.length; i++) {
for (let j = coins[i]; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1)
}
// console.log(i,coins[i],dp)
}
return dp[amount] === Number.POSITIVE_INFINITY ? -1 : dp[amount]
};
coinChange([1,2,5], 11)
0 1 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
1 2 [ 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6 ]
2 5 [ 0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3 ]279. 完全平方数
https://leetcode.cn/problems/perfect-squares/description/
var numSquares = function(n) {
// 前一选择影响后一步的选择容量等于价值
// 是组合，外层遍历 物品i
// 是完全背包，内层正序遍历 容量j
// dp[i]: 和为i的最少完全平方数的数量
// dp[i] = Math.min(dp[i], dp[j - Math.pow(i,2)])
const dp = new Array(n+1).fill(Number.POSITIVE_INFINITY)
dp[0] = 0
for(let i = 1; i <= Math.sqrt(n); i++) {
const weight = Math.pow(i,2)
for(let j = weight; j <= n; j++) {
dp[j] = Math.min(dp[j], dp[j - weight] + 1)
}
}
return dp[n]
};139. 单词拆分
https://leetcode.cn/problems/word-break/description/
var wordBreak = function (s, wordDict) {
// 是排列，外层循环 重量j
// 是完全背包，内层正序循环
// dp[i] 为true，代表 前s[i] 可以被 wordDict表示
const dp = new Array(s.length + 1).fill(false)
dp[0] = true
// 前s[i]
for (let i = 1; i <= s.length; i++) {
const si = s.slice(0, i)
// 从前向后找，每s[i]遍历wordDict，看能不能实现前s[i]
for (let j = 0; j < wordDict.length; j++) {
// 以前到这个容量行，不然就把当前word放进末尾，在看前i是否为true
const length = wordDict[j].length
dp[i] = dp[i] || i >= length && s.slice(i - length, i) === wordDict[j] && dp[i - length]
}
}
return dp[s.length]
};——– 多重背包 ——–
多重背包 就是 完全背包但数量有限，其按数量摊开可视为01背包
解法为在01背包的基础上 再加一层循环，针对 每个物品i的数量进行循环
function testMultiPack() {
const bagSize = 10;
const weightArr = [1, 3, 4], valueArr = [15, 20, 30], amountArr = [2, 3, 2];
const goodsNum = weightArr.length;
const dp = new Array(bagSize + 1).fill(0);
// 遍历物品
for (let i = 0; i < goodsNum; i++) {
// 遍历物品个数
for (let j = 0; j < amountArr[i]; j++) {
// 遍历背包容量
for (let k = bagSize; k >= weightArr[i]; k--) {
dp[k] = Math.max(dp[k], dp[k - weightArr[i]] + valueArr[i]);
}
console.log(i,j,valueArr[i],dp);
}
}
}
testMultiPack();
0 0 15 [ 0, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15 ]
0 1 15 [ 0, 15, 30, 30, 30, 30, 30, 30, 30, 30, 30 ]
1 0 20 [ 0, 15, 30, 30, 35, 50, 50, 50, 50, 50, 50 ]
1 1 20 [ 0, 15, 30, 30, 35, 50, 50, 55, 70, 70, 70 ]
1 2 20 [ 0, 15, 30, 30, 35, 50, 50, 55, 70, 70, 75 ]
2 0 30 [ 0, 15, 30, 30, 35, 50, 60, 60, 70, 80, 80 ]
2 1 30 [ 0, 15, 30, 30, 35, 50, 60, 60, 70, 80, 90 ]代码随想录递推公式总结篇
198.打家劫舍
https://leetcode.cn/problems/house-robber/description/
var rob = function(nums) {
// dp[i] 前i最多打到dp[i]
// 如果不偷i, dp[i] = dp[i - 1]
// 如果偷i， dp[i] = dp[i - 2] + nums[i]
// 从下标2开始遍历, 所以要确定 0 1
// dp[0] 就是nums[0]， dp[1]是max(nums[0], nums[1])
const dp = [nums[0], Math.max(nums[0], nums[1])];
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
};
rob(
[ 2, 7, 9, 3, 1 ]
)
[ 2, 7, 11, 11, 12 ]213.打家劫舍II
https://leetcode.cn/problems/house-robber-ii/description/
var rob = function (nums) {
// 多了一层选首不能选尾，选尾不能选首，也即多一个max
if (nums.length === 1) return nums[0]
const front = robRange(nums, 0, nums.length - 2)
const end = robRange(nums, 1, nums.length - 1)
return Math.max(front, end)
};
// s -> startIndex e -> endIndex
const robRange = (nums, s, e) => {
if (s === e) return nums[s]
// 这里必须nums.length创建array，因为dp得和nums的i对应上
const dp = Array(nums.length).fill(0)
dp[s] = nums[s]
dp[s + 1] = Math.max(nums[s], nums[s + 1])
for (let i = s + 2; i <= e; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
}
// console.log(dp);
return dp[e]
}
rob(
[ 2, 3, 2 ]
)
[ 2, 3, 0 ]
[ 0, 3, 3 ]337. 打家劫舍 III
https://leetcode.cn/problems/house-robber-iii/description/
const rob = root => {
// 后序遍历函数
const postOrder = node => {
// 递归出口
if (!node) return [0, 0];
// 遍历左子树
const left = postOrder(node.left);
// 遍历右子树
const right = postOrder(node.right);
// 不偷当前节点，左右子节点都可以偷或不偷，取最大值
const DoNot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
// 偷当前节点，左右子节点只能不偷
const Do = node.val + left[0] + right[0];
// [不偷，偷]
return [DoNot, Do];
};
const res = postOrder(root);
// 返回最大值
return Math.max(...res);
};——买卖股票——
121.买卖股票的最佳时机
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
var maxProfit = function (prices) {
// 只能买卖一次，假设昨天是卖出的状态，那今天再买入就只有-prices[i],
const l = prices.length
const dp = new Array(l).fill(0).map(() => new Array(2).fill(0))
dp[0][1] = -prices[0]
dp[0][0] = 0
for (let i = 1; i < l; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
}
return dp[l - 1][0]
};
// maxProfit([7, 1, 5, 3, 6, 4])
// dp: [[-7, 0], [-1, 0], [-1, 4], [-1, 4], [-1, 5], [-1, 5]]var maxProfit = function (prices) {
let hold = -prices[0]
let not = 0
for(let i = 1; i < prices.length; i++) {
not = Math.max(not, hold + prices[i])
hold = Math.max(hold, -prices[i])
}
return not
};动态规划 本质上是遍历了所有情况，但是由于动态规划对前期每一步的情况，都进行了储存，
使得后续的遍历，减少了重复的计算
就是每一步状态都由上一步推导出来，动态规划，就是每走一步都进行规划，进行计算。
区分于贪心，贪心没有状态推导，而是从局部直接选最优的，
122. 买卖股票的最佳时机 II
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
var maxProfit = function (prices) {
// dp[i] 前i天能获取的最大利润
// 对于遍历到的当前i，可以选择
// 不持有i， dp[i][0] = dp[i-1][0],dp[i-1][1] + prices[i]
// 持有i, dp[i][1] = dp[i-1][1],dp[i-1][0] - prices[i]
// const dp = new Array(prices.length).fill(0).map(() => new Array(2).fill(0))
// dp[0][0] = 0
// dp[0][1] = -prices[0]
let dontHold = 0
let hold = -prices[0]
for(let i = 1; i < prices.length; i++) {
// dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])
// dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i])
dontHold = Math.max(dontHold, hold + prices[i])
hold = Math.max(hold, dontHold - prices[i])
}
return dontHold
};
console.log(maxProfit([7, 1, 5, 3, 6, 4]))123. 买卖股票的最佳时机 III
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
const maxProfit = prices => {
const len = prices.length;
const dp = new Array(len).fill(0).map(x => new Array(5).fill(0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (let i = 1; i < len; i++) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 保持第一次持有，或从第一次不持有到第一次持有
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]); // 保持第一次不持有，或从第一次持有到第一次不持有
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]); // 保持第二次持有，或从第一次不持有到第二次持有
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]); // 保持第二次不持有，或从第二次持有到第二次不持有
}
// 第一次卖出和第二次卖出，并不需要状态判断，前期 第一次和第二次 可视为同线操作。
// 只需要一次买卖的情况，dp[l-1][4] 和 dp[l-1][2] 是相等的
return dp[len - 1][4];
};
// maxProfit([2,1,4,5,2,9,7])const maxProfit = prices => {
const len = prices.length;
const dp = new Array(5).fill(0);
dp[1] = -prices[0];
dp[3] = -prices[0];
for (let i = 1; i < len; i++) {
dp[1] = Math.max(dp[1], dp[0] - prices[i]);
dp[2] = Math.max(dp[2], dp[1] + prices[i]);
dp[3] = Math.max(dp[3], dp[2] - prices[i]);
dp[4] = Math.max(dp[4], dp[3] + prices[i]);
}
return dp[4];
};188. 买卖股票的最佳时机 IV
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
var maxProfit = function (k, prices) {
const l = prices.length
const status = 2 * k + 1
const dp = new Array(status).fill(0)
// 所有持有初始为 - prices[0]
for (let k = 1; k < status; k += 2) dp[k] = - prices[0]
for (let i = 0; i < prices.length; i++) {
// 有点顺应排列，从前往后遍历的感觉
for (let j = 1; j < status; j++) {
const holdOrNot = j % 2 === 1 ? (dp[j - 1] - prices[i]) : (dp[j - 1] + prices[i])
dp[j] = Math.max(dp[j], holdOrNot)
}
}
return dp[status - 1]
};
maxProfit([3, 2, 6, 5, 0, 3])
309. 买卖股票的最佳时机含冷冻期
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
var maxProfit = function (prices) {
const l = prices.length
const dp = new Array(l).fill(0).map(() => new Array(4).fill(0))
dp[0][0] = -prices[0] // 持有
// 0持有 = 前一天是， 持有 或 当天买入(保持不持有) 或 当天买入(冷静期)
// 1保持不持有 = 前一天是， 保持不持有 或 冷静期
// 2当天卖出 = 前一天是， 持有
// 3冷静期 = 前一天是， 当天卖出
for (let i = 1; i < l; i++) {
dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3]) - prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3])
dp[i][2] = dp[i - 1][0] + prices[i]
dp[i][3] = dp[i - 1][2]
}
return Math.max(dp[l - 1][1], dp[l - 1][2], dp[l - 1][3])
};714. 买卖股票的最佳时机含手续费
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
var maxProfit = function (prices, fee) {
let hold = -prices[0] - fee
let not = 0
for (let i = 1; i < prices.length; i++) {
hold = Math.max(hold, not - prices[i] - fee)
not = Math.max(not, hold + prices[i])
}
return not
};var maxProfit = function (prices, fee) {
const l = prices.length
const dp = new Array(l).fill(0).map(() => new Array(2).fill(0))
dp[0][0] = 0
dp[0][1] = -prices[0] - fee
for (let i = 1; i < l; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
}
return dp[l - 1][0]
};300. 最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence/submissions/476442040/
const lengthOfLIS = (nums) => {
// dp[i] 以dp[i]结尾 的最长严格递增子序列长度
// dp[i] = 前i-1中 满足尾数小于当前数 num[j] < num[i] 中的最大值+1
let dp = Array(nums.length).fill(1);
let result = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
result = Math.max(result, dp[i]);
}
return result;
};
lengthOfLIS([1, 3, 6, 7, 9, 4, 10, 5, 6])
// [ 1, 2, 3, 4, 5, 3, 6, 4, 5 ]674. 最长连续递增序列
https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/
1var findLengthOfLCIS = function (nums) {
// 要求连续，那就是以i-1为基础计算i
let pre = 1, max = 0
for (let i = 1; i < nums.length; i++) {
const cur = nums[i - 1] < nums[i] ? pre + 1 : 1
max = Math.max(max, cur)
pre = cur
}
return max
};718. 最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
const findLength = (nums1, nums2) => {
const [m, n] = [nums1.length, nums2.length];
const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0));
let res = 0;
// 用二维数组记录所有比较情况
// dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
// 递推公式需要用到i-1，所以要初始化0位置，并从1位置开始
for (let i = 1; i <= m; i++) {
// 每放入一个nums1[i],遍历nums2[j],找有没有跟自己相等的,有就是当前dp+1
for (let j = 1; j <= n; j++) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
res = dp[i][j] > res ? dp[i][j] : res;
}
}
return res;
};
const findLength2 = (nums1, nums2) => {
const [m, n] = [nums1.length, nums2.length];
const dp = new Array(m + 1).fill(0)
let res = 0;
// 由于每次都只需要用到i-1层，可使用滚动数组
// 由于是组合问题，需要内层倒序
for (let i = 1; i <= m; i++) {
for (let j = n; j > 0; j--) {
dp[j] = nums1[i - 1] === nums2[j - 1] ? dp[j - 1] + 1 : 0
res = Math.max(res, dp[j])
}
console.log(dp)
}
return res;
};
findLength2([1, 2, 3, 2, 1], [3, 2, 1, 4, 7])
3, 2, 1, 4, 7
[ 0, 0, 0, 1, 0, 0 ]
1 [ 0, 0, 0, 1, 0, 0 ]
2 [ 0, 0, 1, 0, 0, 0 ]
3 [ 0, 1, 0, 0, 0, 0 ]
2 [ 0, 0, 2, 0, 0, 0 ]
1 [ 0, 0, 0, 3, 0, 0 ]1143. 最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence/description/
const longestCommonSubsequence = (text1, text2) => {
// dp[i][j] text1中的前i 和 text2中的前j 的公共子序列最长长度
let dp = Array.from(Array(text1.length+1), () => Array(text2.length+1).fill(0));
for(let i = 1; i <= text1.length; i++) {
for(let j = 1; j <= text2.length; j++) {
if(text1[i-1] === text2[j-1]) {
dp[i][j] = dp[i-1][j-1] +1;;
} else {
// 如果不相等，那就通过i延伸，或者通过j延伸
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[text1.length][text2.length];
};
longestCommonSubsequence("abcde","ace")
[
a c e
[ 0, 0, 0, 0 ],
a [ 0, 1, 1, 1 ],
b [ 0, 1, 1, 1 ],
c [ 0, 1, 2, 2 ],
d [ 0, 1, 2, 2 ],
e [ 0, 1, 2, 3 ]
]1035.不相交的线
https://leetcode.cn/problems/uncrossed-lines/description/
var maxUncrossedLines = function (nums1, nums2) {
// 找相同元素连线，而线不相交
// 也即，在两个数组间，找相同顺序的子序列,也即最长公共子序列
const dp = new Array(nums1.length + 1).fill(0).map(() => new Array(nums2.length + 1).fill(0))
for(let i = 1; i <= nums1.length; i++) {
for(let j = 1; j <= nums2.length; j++) {
// 考虑顺序，也即排列，每次的计算都基于当前轮的计算，最新j的排列
if(nums1[i-1] === nums2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1
} else {
// 如果不相等，就考虑采用i更多，还是采用j更多,双重动态规划
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
}
}
}
return dp[nums1.length][nums2.length]
};53. 最大子序和
https://leetcode.cn/problems/maximum-subarray/
var maxSubArray = function (nums) {
// 连续：基于上一个计算，并且是排列
let pre = max = Number.NEGATIVE_INFINITY
// 如果pre + nums[i] 还没nums[i]大，那nums[i]就是新的头
for (const item of nums) {
pre = Math.max(item, pre + item)
max = Math.max(max, pre)
}
return max
};// 标准动态规划
const maxSubArray = nums => {
const len = nums.length;
let dp = new Array(len).fill(0);
dp[0] = nums[0];
let max = dp[0];
for (let i = 1; i < len; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
max = Math.max(max, dp[i]);
}
return max;
};392.判断子序列
https://leetcode.cn/problems/is-subsequence/
const isSubsequence = (s, t) => {
// 1143.最长公共子序列的递推公式基本一样，区别是本题如果删元素一定是字符串t
// dp[i][j] = dp[i-1][j-1] + 1
// dp[i][j] = dp[i][j-1]
const dp = new Array(s.length + 1).fill(0).map(() => new Array(t.length + 1).fill(0))
for (let i = 1; i <= s.length; i++) {
// 针对每个i遍历j，找有没有相等的，有相等的就在上一轮的基础+1
// 如果存在i遍历j，都没找到，则都是0.则后续也全为0
for (let j = 1; j <= t.length; j++) {
if (s[i - 1] === t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = dp[i][j - 1]
}
}
}
return dp[s.length][t.length] === s.length
};
// 每次都不是 只需要上一层，或者说左上角的数据，所以不可以用滚动数组优化
// dp[i-1] 和 dp[i] 都要用到
isSubsequence("abc", "ahbgdc")
[
[0, 0, 0, 0, 0, 0, 0],
a[0, 1, 1, 1, 1, 1, 1],
b[0, 0, 0, 2, 2, 2, 2],
c[0, 0, 0, 0, 0, 0, 3]
]// 其实只要按顺序能在t中找到所有s就行，遍历s，在t中按顺序找
var isSubsequence = function(s, t) {
let i = j = 0
for(; j < t.length; j++) s[i] === t[j] && i++
return i === s.length
};115.不同的子序列
var numDistinct = function (s, t) {
// dp[i][j] i中出现了j多少次
// s[i-1] === t[j-1]
// dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] 代表继承数量 + 前面匹配上的次数
// dp[i][j] = dp[i - 1][j] 代表 新进的j和i不匹配，数量不加减
// 不能用滚动数组化简，因为需要用到当前层前面的j
const dp = new Array(s.length + 1).fill(0).map(() => new Array(t.length + 1).fill(0))
// s中找 t长度为0，初始化为1
for (let i = 0; i <= s.length; i++) {
dp[i][0] = 1;
}
for (let i = 1; i <= s.length; i++) {
for (let j = 1; j <= t.length; j++) {
if (s[i - 1] === t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
} else {
dp[i][j] = dp[i - 1][j]
}
}
}
console.log(dp)
return dp[s.length][t.length]
};
numDistinct("rabbbit","rabbit")
[
r, a, b, b, i, t
[ 1, 0, 0, 0, 0, 0, 0 ],
r[ 1, 1, 0, 0, 0, 0, 0 ],
a[ 1, 1, 1, 0, 0, 0, 0 ],
b[ 1, 1, 1, 1, 0, 0, 0 ],
b[ 1, 1, 1, 2, 1, 0, 0 ],
b[ 1, 1, 1, 3, 3, 0, 0 ],
i[ 1, 1, 1, 3, 3, 3, 0 ],
t[ 1, 1, 1, 3, 3, 3, 3 ]
]
