什么是动态规划
动态规划，英文：Dynamic Programming，简称DP，将问题分解为互相重叠的子问题，通过反复求解子问题来解决原问题就是动态规划，如果某一问题有很多重叠子问题，使用动态规划来解是比较有效的。
求解动态规划的核心问题是穷举，但是这类问题穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。重叠子问题、最优子结构、状态转移方程就是动态规划三要素
动态规划和其他算法的区别
动态规划和分治的区别：动态规划和分治都有最优子结构 ，但是分治的子问题不重叠
动态规划和贪心的区别：动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优解，所以它永远是局部最优，但是全局的解不一定是最优的。
动态规划和递归的区别：递归和回溯可能存在非常多的重复计算，动态规划可以用递归加记忆化的方式减少不必要的重复计算
动态规划的解题方法
解动态规划题目的步骤
根据重叠子问题定义状态
寻找最优子结构推导状态转移方程
确定 dp 初始状态
确定输出值
斐波那契的动态规划的解题思路
动画过大，点击查看
暴力递归
//暴力递归复杂度O(2^n)var fib = function (N) { if (N == 0) return 0; if (N == 1) return 1; return fib(N - 1) + fib(N - 2);};
复制代码
递归 + 记忆化
var fib = function (n) { const memo = {}; // 对已算出的结果进行缓存
const helper = (x) => { if (memo[x]) return memo[x]; if (x == 0) return 0; if (x == 1) return 1; memo[x] = helper(x - 1) + helper(x - 2); return memo[x]; };
return helper(n);};
复制代码
动态规划
const fib = (n) => { if (n <= 1) return n; const dp = [0, 1]; for (let i = 2; i <= n; i++) { //自底向上计算每个状态 dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];};
复制代码
滚动数组优化
const fib = (n) => { if (n <= 1) return n; //滚动数组 dp[i]只和dp[i-1]、dp[i-2]相关，只维护长度为2的滚动数组，不断替换数组元素 const dp = [0, 1]; let sum = null; for (let i = 2; i <= n; i++) { sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return sum;};
复制代码
动态规划 + 降维，（降维能减少空间复杂度，但不利于程序的扩展）
var fib = function (N) { if (N <= 1) { return N; } let prev2 = 0; let prev1 = 1; let result = 0; for (let i = 2; i <= N; i++) { result = prev1 + prev2; //直接用两个变量就行 prev2 = prev1; prev1 = result; } return result;};
复制代码
0-1 背包问题
0-1 背包问题指的是有n个物品和容量为j的背包，weight数组中记录了n个物品的重量，位置i的物品重量是 weight[i]，value数组中记录了n个物品的价值，位置 i 的物品价值是vales[i]，每个物品只能放一次到背包中，问将那些物品装入背包，使背包的价值最大。
举例：
我们用动态规划的方式来做
状态定义：dp[i][j] 表示从前 i 个物品里任意取，放进容量为 j 的背包，价值总和最大是多少
状态转移方程： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 每个物品有放入背包和不放入背包两种情况
当j - weight[i]<0：表示装不下i号元素了，不放入背包，此时dp[i][j] = dp[i - 1][j]，dp[i] [j]取决于前i-1中的物品装入容量为j的背包中的最大价值
当j - weight[i]>=0：可以选择放入或者不放入背包。放入背包则：dp[i][j] = dp[i - 1][j - weight[i]] + value[i]， dp[i - 1][j - weight[i]] 表示i-1中的物品装入容量为j-weight[i]的背包中的最大价值，然后在加上放入的物品的价值value[i]就可以将状态转移到dp[i][j]。不放入背包则：dp[i][j] = dp[i - 1] [j]，在这两种情况中取较大者。
初始化 dp 数组：dp[i][0]表示背包的容积为 0，则背包的价值一定是 0，dp[0][j]表示第 0 号物品放入背包之后背包的价值
最终需要返回值：就是 dp 数组的最后一行的最后一列
循环完成之后的 dp 数组如下图
js：
function testWeightBagProblem(wight, value, size) { const len = wight.length, dp = Array.from({ length: len + 1 }).map(//初始化dp数组 () => Array(size + 1).fill(0) ); //注意我们让i从1开始，因为我们有时会用到i - 1，为了防止数组越界 //所以dp数组在初始化的时候，长度是wight.length+1 for (let i = 1; i <= len; i++) { for (let j = 0; j <= size; j++) { //因为weight的长度是wight.length+1，并且物品下标从1开始，所以这里i要减1 if (wight[i - 1] <= j) { dp[i][j] = Math.max( dp[i - 1][j], value[i - 1] + dp[i - 1][j - wight[i - 1]] ) } else { dp[i][j] = dp[i - 1][j]; } } }
return dp[len][size];}
function test() { console.log(testWeightBagProblem([1, 3, 4], [15, 20, 30], 4));}
test();
复制代码
状态压缩
根据状态转移方程dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，第 i 行只与第 i-1 行状态相关，所以我们可以用滚动数组进行状态压缩，其次我们注意到，j 只与 j 前面的状态相关，所以只用一个数组从后向前计算状态就可以了。
动画过大，点击查看
function testWeightBagProblem2(wight, value, size) { const len = wight.length, dp = Array(size + 1).fill(0); for (let i = 1; i <= len; i++) { //从后向前计算，如果从前向后的话，最新的值会覆盖老的值，导致计算结果不正确 //dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wight[i - 1]] + value[i - 1]) for (let j = size; j >= wight[i - 1]; j--) { dp[j] = Math.max(dp[j], dp[j - wight[i - 1]] + value[i - 1] ); } } return dp[size];}
复制代码
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2：
输入：nums = [1,2,3,5]输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
思路：本题可以看成是 0-1 背包问题，给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量记录在 nums 数组中，问是否在一种装法，能够恰好将背包装满？dp[i][j]表示前 i 个物品是否能装满容积为 j 的背包，当dp[i][j]为 true 时表示恰好可以装满。每个数都有放入背包和不放入两种情况，分析方法和 0-1 背包问题一样。
复杂度：时间复杂度O(n*sum)，n 是 nums 数组长度，sum 是 nums 数组元素的和。空间复杂度O(n * sum)，状态压缩之后是O(sum)
js：
//可以看成是0-1背包问题，给一个可装载重量为 sum / 2 的背包和 N 个物品，//每个物品的重量记录在 nums 数组中，问是否在一种装法，能够恰好将背包装满？var canPartition = function (nums) { let sum = 0 let n = nums.length for (let i = 0; i < n; i++) { sum += nums[i] } if (sum % 2 !== 0) {//如果是奇数，那么分割不了，直接返回false return false } sum = sum / 2 //dp[i][j]表示前i个物品是否能装满容积为j的背包，当dp[i][j]为true时表示恰好可以装满 //最后求的是 dp[n][sum] 表示前n个物品能否把容量为sum的背包恰好装满 //dp数组长度是n+1，而且是二维数组，第一维表示物品的索引，第二个维度表示背包大小 let dp = new Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(false)) //dp数组初始化，dp[..][0] = true表示背包容量为0，这时候就已经装满了， //dp[0][..] = false 表示没有物品，肯定装不满 for (let i = 0; i <= n; i++) { dp[i][0] = true } for (let i = 1; i <= n; i++) {//i从1开始遍历防止取dp[i - 1][j]的时候数组越界 let num = nums[i - 1] //j从1开始，j为0的情况已经在dp数组初始化的时候完成了 for (let j = 1; j <= sum; j++) { if (j - num < 0) {//背包容量不足 不能放入背包 dp[i][j] = dp[i - 1][j];//dp[i][j]取决于前i-1个物品是否能前好装满j的容量 } else { //dp[i - 1][j]表示不装入第i个物品 //dp[i - 1][j-num]表示装入第i个，此时需要向前看前i - 1是否能装满j-num //和背包的区别，这里只是返回true和false 表示能否装满，不用计算价值 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num]; } } } return dp[n][sum]};
//状态转移方程 F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]//第 n 行的状态只依赖于第 n-1 行的状态//状态压缩var canPartition = function (nums) { let sum = nums.reduce((acc, num) => acc + num, 0); if (sum % 2) { return false; } sum = sum / 2; const dp = Array.from({ length: sum + 1 }).fill(false); dp[0] = true;
for (let i = 1; i <= nums.length; i++) { //从后向前计算，如果从前向后的话，最新的值会覆盖老的值，导致计算结果不正确 for (let j = sum; j > 0; j--) { dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]); } }
return dp[sum];};
复制代码
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7 解释：因为路径 1→3→1→1→1 的总和最小。示例 2：
输入：grid = [[1,2,3],[4,5,6]]输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
js：
var minPathSum = function(dp) { let row = dp.length, col = dp[0].length
for(let i = 1; i < row; i++)//初始化第一列 dp[i][0] += dp[i - 1][0]
for(let j = 1; j < col; j++)//初始化第一行 dp[0][j] += dp[0][j - 1]
for(let i = 1; i < row; i++) for(let j = 1; j < col; j++) dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1])//取上面和左边最小的
return dp[row - 1][col - 1]};
复制代码
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]输出：11 解释：如下面简图所示： 2 3 4 6 5 74 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。示例 2：
输入：triangle = [[-10]]输出：-10
提示：
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
方法 1.动态规划
Js:
const minimumTotal = (triangle) => { const h = triangle.length; // 初始化dp数组 const dp = new Array(h); for (let i = 0; i < h; i++) { dp[i] = new Array(triangle[i].length); }
for (let i = h - 1; i >= 0; i--) { //自底而上遍历 for (let j = 0; j < triangle[i].length; j++) { //同一层的 if (i == h - 1) { // base case 最底层 dp[i][j] = triangle[i][j]; } else { // 状态转移方程，上一层由它下面一层计算出 dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]; } } } return dp[0][0];};
//状态压缩const minimumTotal = (triangle) => { const bottom = triangle[triangle.length - 1]; const dp = new Array(bottom.length); // base case 是最后一行 for (let i = 0; i < dp.length; i++) { dp[i] = bottom[i]; } // 从倒数第二列开始迭代 for (let i = dp.length - 2; i >= 0; i--) { for (let j = 0; j < triangle[i].length; j++) { dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j]; } } return dp[0];};
复制代码
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4 示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9 提示：
1 <= n <= 104
方法 1:动态规划
思路：dp[i] 表示i的完全平方和的最少数量，dp[i - j * j] + 1表示减去一个完全平方数j的完全平方之后的数量加 1 就等于dp[i]，只要在dp[i], dp[i - j * j] + 1中寻找一个较少的就是最后dp[i]的值。
复杂度：时间复杂度O(n* sqrt(n))，n是输入的整数，需要循环n次，每次计算dp方程的复杂度sqrt(n)，空间复杂度O(n)
js：
var numSquares = function (n) { const dp = [...Array(n)].map((_) => 0); //初始化dp数组 当n为0的时候 for (let i = 1; i <= n; i++) { dp[i] = i; // 最坏的情况就是每次+1 比如: dp[3]=1+1+1 for (let j = 1; i - j * j >= 0; j++) {//枚举前一个状态 dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程 } } return dp[n];};
复制代码
买卖股票问题
第 5，6 道题相当于在第 2 道题的基础上加了冷冻期和手续费的条件。
限制条件
先买入才能卖出
不能同时参加多笔交易，再次买入时，需要先卖出
k >= 0才能进行交易，否则没有交易次数
定义操作
定义状态
举例
dp[i][k][0]//第i天 还可以交易k次 手中没有股票 dp[i][k][1]//第i天 还可以交易k次 手中有股票
复制代码
最终的最大收益是dp[n - 1][k][0]而不是dp[n - 1][k][1]，因为最后一天卖出肯定比持有收益更高
状态转移方程
// 今天没有持有股票，分为两种情况：// 1. dp[i - 1][k][0]，昨天没有持有，今天不操作。 // 2. dp[i - 1][k][1] + prices[i] 昨天持有，今天卖出，今天手中就没有股票了。dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
// 今天持有股票，分为两种情况：// 1.dp[i - 1][k][1] 昨天持有，今天不操作// 2.dp[i - 1][k - 1][0] - prices[i] 昨天没有持有，今天买入。dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
//最大利润就是这俩种情况的最大值
复制代码
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输入：prices = [7,6,4,3,1]输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
状态转移方程
//第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后卖出 两种情况的最大值转移过来dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])//第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后买入 两种情况的最大值转移过来dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = Math.max(dp[i - 1][1][1], -prices[i]) // k=0时 没有交易次数，dp[i - 1][0][0] = 0
复制代码
k是固定值 1，不影响结果，所以可以不用管，简化之后如下
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])
复制代码
完整代码
//时间复杂度O(n) 空间复杂度O(n)，dp数组第二维是常数const maxProfit = function (prices) { let n = prices.length; let dp = Array.from(new Array(n), () => new Array(2)); dp[0][0] = 0; //第0天不持有 dp[0][1] = -prices[0]; //第0天持有 for (let i = 1; i < n; 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[n - 1][0];};
复制代码
状态压缩，dp[i] 只和 dp[i - 1] 有关，去掉一维
//时间复杂度O(n) 空间复杂度O(1)const maxProfit = function (prices) { let n = prices.length; let dp = Array.from(new Array(n), () => new Array(2)); dp[0] = 0; dp[1] = -prices[0]; for (let i = 1; i < n; i++) { dp[0] = Math.max(dp[0], dp[1] + prices[i]); dp[1] = Math.max(dp[1], -prices[i]); } return dp[0];};
//语意化const maxProfit = function (prices) { let n = prices.length; let sell = 0; let buy = -prices[0]; for (let i = 1; i < n; i++) { sell = Math.max(sell, buy + prices[i]); buy = Math.max(buy, -prices[i]); } return sell;};
复制代码
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。示例 2：
输入：prices = [1,2,3,4,5]输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 总利润为 4 。示例 3：
输入：prices = [7,6,4,3,1]输出：0 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
提示：
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
状态转移方程
//第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后卖出 两种情况的最大值转移过来dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])//第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后买入 两种情况的最大值转移过来dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
复制代码
k 同样不影响结果，简化之后如下
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])
复制代码
完整代码
const maxProfit = function (prices) { let n = prices.length; let dp = Array.from(new Array(n), () => new Array(2)); dp[0][0] = 0; //第0天不持有 dp[0][1] = -prices[0]; //第0天买入 花了prices[0] for (let i = 1; i < n; 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]); } return dp[n - 1][0];};
复制代码
状态压缩，同样dp[i] 只和 dp[i - 1] 有关，去掉一维
const maxProfit = function (prices) { let n = prices.length; let dp = Array.from(new Array(n), () => new Array(2)); dp[0] = 0; dp[1] = -prices[0]; for (let i = 1; i < n; i++) { dp[0] = Math.max(dp[0], dp[1] + prices[i]); dp[1] = Math.max(dp[1], dp[0] - prices[i]); } return dp[0];};
//语意化const maxProfit = function (prices) { let n = prices.length; let sell = 0; let buy = -prices[0]; for (let i = 1; i < n; i++) { sell = Math.max(sell, buy + prices[i]); buy = Math.max(buy, sell - prices[i]); } return sell;};
复制代码
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。示例 2：
输入：prices = [1,2,3,4,5]输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。示例 4：
输入：prices = [1]输出：0
提示：
1 <= prices.length <= 1050 <= prices[i] <= 105
状态转移方程
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
复制代码
k 对结果有影响 不能舍去，只能对 k 进行循环
for (let i = 0; i < n; i++) { for (let k = maxK; k >= 1; k--) { dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]); dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]); }}
//k=2，直接写出循环的结果dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = Math.max(dp[i - 1][1][1], -prices[i])// k=0时 没有交易次数，dp[i - 1][0][0] = 0
//去掉i这一维度dp[2][0] = Math.max(dp[2][0], dp[2][1] + prices[i])dp[2][1] = Math.max(dp[2][1], dp[1][0] - prices[i])
dp[1][0] = Math.max(dp[1][0], dp[1][1] + prices[i])dp[1][1] = Math.max(dp[1][1], dp[0][0] - prices[i]) = Math.max(dp[1][1], -prices[i])// k=0时 没有交易次数，dp[i - 1][0][0] = 0
复制代码
完整代码
//和前面一样 我们直接降维const maxProfit = function (prices) { let buy_1 = -prices[0], sell_1 = 0 let buy_2 = -prices[0], sell_2 = 0 let n = prices.length for (let i = 1; i < n; i++) { sell_2 = Math.max(sell_2, buy_2 + prices[i]) buy_2 = Math.max(buy_2, sell_1 - prices[i]) sell_1 = Math.max(sell_1, buy_1 + prices[i]) buy_1 = Math.max(buy_1, -prices[i]) } return sell_2}
复制代码
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
0 <= k <= 1000 <= prices.length <= 10000 <= prices[i] <= 1000
const maxProfit = function (k, prices) { let n = prices.length; let profit = new Array(k);//和123题一样 求出所有k的状态 // 初始化k次交易买入卖出的利润 for (let j = 0; j <= k; j++) { profit[j] = { buy: -prices[0],//表示有股票 sell: 0,//表示没有股票 }; } for (let i = 0; i < n; i++) { for (let j = 1; j <= k; j++) { //122题可以交易无数次，188交易k次，所以直接在加一层k循环就可以 //122最后的递推方程： //sell = Math.max(sell, buy + prices[i]); //buy = Math.max(buy, -prices[i]); profit[j] = { sell: Math.max(profit[j].sell, profit[j].buy + prices[i]), buy: Math.max(profit[j].buy, profit[j - 1].sell - prices[i]), }; } } return profit[k].sell; //返回第k次清空手中的股票之后的最大利润};
复制代码
给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:
输入: prices = [1]输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
状态转移方程
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])//冷却时间1天，所以要从 i - 2 天转移状态//买入，卖出 ---- 冷冻期 ---- 买入，卖出dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
复制代码
题目不限制 k 的大小，可以舍去
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 - 2][0] - prices[i])
//降维idp[0] = Math.max(dp[0], dp[1] + prices[i])dp[1] = Math.max(dp[1], profit_freeze - prices[i])
复制代码
完整代码
const maxProfit = function (prices) { let n = prices.length; let buy = -prices[0];//手中有股票 let sell = 0;//没有股票 let profit_freeze = 0; for (let i = 1; i < n; i++) { let temp = sell; sell = Math.max(sell, buy + prices[i]); buy = Math.max(buy, profit_freeze - prices[i]); profit_freeze = temp; } return sell;};
复制代码
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润:
在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8 示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
提示：
1 <= prices.length <= 5 * 1041 <= prices[i] < 5 * 1040 <= fee < 5 * 104
状态转移方程
//每次交易要支付手续费 我们定义在卖出的时候扣手续费dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
复制代码
完整代码
const maxProfit = function (prices, fee) { let sell = 0;//卖出 let buy = -prices[0];//买入 for (let i = 1; i < prices.length; i++) { sell = Math.max(sell, buy + prices[i] - fee); buy = Math.max(buy, sell - prices[i]); } return sell;};
复制代码
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1 示例 2：
输入：coins = [2], amount = 3 输出：-1 示例 3：
输入：coins = [1], amount = 0 输出：0
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
不能用贪心做，反例，coins=[1, 3, 5, 6, 7]，amount=30，用贪心先用最大的面额 7，在用 2 个 1，4 * 7 + 2 * 1 = 30，但是我们用 5 个 6，5 * 6 = 30 就能用最少的硬币兑换完成
方法 1.动态规划
思路：dp[i]表示兑换面额i所需要的最少硬币，因为硬币无限，所以可以自底向上计算dp[i]，对于dp[0~i]的每个状态，循环coins数组，寻找可以兑换的组合，用i面额减去当前硬币价值，dp[i-coin]在加上一个硬币数就是dp[i],最后取最小值就是答案，状态转移方程就是dp[i] = Math.min(dp[i], dp[i - coin] + 1);
复杂度分析：时间复杂度是 O(sn)，s 是兑换金额，n 是硬币数组长度，一共需要计算 s 个状态，每个状态需要遍历 n 个面额来转移状态。空间复杂度是O(s)，也就是 dp 数组的长度
Js:
var coinChange = function (coins, amount) { let dp = new Array(amount + 1).fill(Infinity);//初始化dp数组 dp[0] = 0;//面额0只需要0个硬币兑换
for (let i = 1; i <= amount; i++) {//循环面额 for (let coin of coins) {//循环硬币数组 if (i - coin >= 0) {//当面额大于硬币价值时 //dp[i - coin]： 当前面额i减当前硬币价值所需要的最少硬币 //dp[i] 可由 dp[i - coin] + 1 转换而来 dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } }
return dp[amount] === Infinity ? -1 : dp[amount];//如果dp[amount] === Infinity，则无法兑换};
复制代码
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
提示：
1 <= n <= 45
方法 1.动态规划
Js:
var climbStairs = function (n) { const memo = []; memo[1] = 1; memo[2] = 2; for (let i = 3; i <= n; i++) { memo[i] = memo[i - 2] + memo[i - 1];//所以到第n阶台阶可以从第n-2或n-1上来 } return memo[n];};
//状态压缩var climbStairs = (n) => { let prev = 1; let cur = 1; for (let i = 2; i < n + 1; i++) { [prev, cur] = [cur, prev + cur] // const temp = cur; // 暂存上一次的cur // cur = prev + cur; // 当前的cur = 上上次cur + 上一次cur // prev = temp; // prev 更新为 上一次的cur } return cur;}
复制代码
有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：输入：nums = [3,1,5,8]输出：167 解释：nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []coins = 315 + 358 + 138 + 181 = 167 示例 2：
输入：nums = [1,5]输出：10
提示：
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
方法 1:动态规划
思路：dp[i][j] 表示开区间 (i,j) 能拿到的的金币，k 是这个区间 最后一个 被戳爆的气球，枚举i和j，遍历所有区间，i-j能获得的最大数量的金币等于 戳破当前的气球获得的金钱加上之前i-k、k-j区间中已经获得的金币
复杂度：时间复杂度O(n^3)，n 是气球的数量，三层遍历。空间复杂度O(n^2)，dp 数组的空间。
js：
var maxCoins = function (nums) { const n = nums.length; let points = [1, ...nums, 1]; //两边添加虚拟气球 const dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0)); //dp数组初始化 //自底向上转移状态 for (let i = n; i >= 0; i--) { //i不断减小 for (let j = i + 1; j < n + 2; j++) { //j不断扩大 for (let k = i + 1; k < j; k++) { //枚举k在i和j中的所有可能 //i-j能获得的最大数量的金币等于 戳破当前的气球获得的金钱加上之前i-k,k-j区间中已经获得的金币 dp[i][j] = Math.max( //挑战最大值 dp[i][j], dp[i][k] + dp[k][j] + points[j] * points[k] * points[i] ); } } } return dp[0][n + 1];};
复制代码
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符'*' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"输出：false 解释："a" 无法匹配 "aa" 整个字符串。示例 2:
输入：s = "aa", p = "a*"输出：true 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3：
输入：s = "ab", p = "."输出：true 解释："." 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
1 <= s.length <= 201 <= p.length <= 30s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母，以及字符 . 和 *。保证每次出现字符 * 时，前面都匹配到有效的字符
方法 1.动态规划
思路：dp[i][j] 表示 s 的前 i 个字符能否和 p 的前 j 个字符匹配，分为四种情况，看图
复杂度：时间复杂度O(mn)，m,n 分别是字符串 s 和 p 的长度，需要嵌套循环 s 和 p。空间复杂度O(mn)，dp 数组所占的空间
js:
//dp[i][j]表示s的前i个字符能否和p的前j个字符匹配const isMatch = (s, p) => { if (s == null || p == null) return false;//极端情况 s和p都是空 返回false
const sLen = s.length, pLen = p.length;
const dp = new Array(sLen + 1);//因为位置是从0开始的，第0个位置是空字符串 所以初始化长度是sLen + 1 for (let i = 0; i < dp.length; i++) {//初始化dp数组 dp[i] = new Array(pLen + 1).fill(false); // 将项默认为false } // base case s和p第0个位置是匹配的 dp[0][0] = true; for (let j = 1; j < pLen + 1; j++) {//初始化dp的第一列，此时s的位置是0 //情况1:如果p的第j-1个位置是*，则j的状态等于j-2的状态 //例如：s='' p='a*' 相当于p向前看2个位置如果匹配，则*相当于重复0个字符 if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2]; } // 迭代 for (let i = 1; i < sLen + 1; i++) { for (let j = 1; j < pLen + 1; j++) {
//情况2:如果s和p当前字符是相等的 或者p当前位置是. 则当前的dp[i][j] 可由dp[i - 1][j - 1]转移过来 //当前位置相匹配，则s和p都向前看一位 如果前面所有字符相匹配 则当前位置前面的所有字符也匹配 //例如：s='XXXa' p='XXX.' 或者 s='XXXa' p='XXXa' if (s[i - 1] == p[j - 1] || p[j - 1] == ".") { dp[i][j] = dp[i - 1][j - 1]; } else if (p[j - 1] == "*") {//情况3:进入当前字符不匹配的分支 如果当前p是* 则有可能会匹配 //s当前位置和p前一个位置相同 或者p前一个位置等于. 则有三种可能 //其中一种情况能匹配 则当前位置的状态也能匹配 //dp[i][j - 2]：p向前看2个位置，相当于*重复了0次， //dp[i][j - 1]：p向前看1个位置，相当于*重复了1次 //dp[i - 1][j]：s向前看一个位置，相当于*重复了n次 //例如 s='XXXa' p='XXXa*' if (s[i - 1] == p[j - 2] || p[j - 2] == ".") { dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j]; } else { //情况4:s当前位置和p前2个位置不匹配，则相当于*重复了0次 //例如 s='XXXb' p='XXXa*' 当前位置的状态和p向前看2个位置的状态相同 dp[i][j] = dp[i][j - 2]; } } } } return dp[sLen][pLen]; // 长为sLen的s串 是否匹配 长为pLen的p串};
复制代码
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
思路：dp[i]为正整数 i 拆分之后的最大乘积，循环数字 n，对每个数字进行拆分，取最大的乘积，状态转移方程：dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)，j*(i-j)表示把 i 拆分为j和 i-j 两个数相乘，j * dp[i-j]表示把i拆分成j和继续把(i-j)这个数拆分，取(i-j)拆分结果中的最大乘积与 j 相乘
复杂度：时间复杂度O(n^2)，两层循环。空间复杂度O(n)，dp数组的空间
js：
var integerBreak = function (n) { //dp[i]为正整数i拆分之后的最大乘积 let dp = new Array(n + 1).fill(0); dp[2] = 1;
for (let i = 3; i <= n; i++) { for (let j = 1; j < i; j++) { //j*(i-j)表示把i拆分为j和i-j两个数相乘 //j*dp[i-j]表示把i拆分成j和继续把(i-j)这个数拆分，取(i-j)拆分结果中的最大乘积与j相乘 dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j); } } return dp[n];};
复制代码
视频讲解：传送门
评论