外贸电子网站,电脑版浏览器入口官网,申请163 com免费邮箱,昆明网红打卡地有哪些地方动态规划在 JavaScript 刷题中有一定的难度#xff0c;但也是非常常见和重要的算法思想。动态规划通常适用于需要求解最优解、最大值、最小值等问题的场景#xff0c;可以将复杂问题拆分成子问题#xff0c;通过存储子问题的解来避免重复计算#xff0c;从而提高效率。 理解… 动态规划在 JavaScript 刷题中有一定的难度但也是非常常见和重要的算法思想。动态规划通常适用于需要求解最优解、最大值、最小值等问题的场景可以将复杂问题拆分成子问题通过存储子问题的解来避免重复计算从而提高效率。 理解问题的状态转移方程 动态规划的核心是找到问题的状态转移方程即如何从子问题的解推导出更大规模问题的解。理解问题的状态转移方程是解决动态规划问题的关键。 定义合适的状态数组 在解决动态规划问题时通常需要定义一个状态数组来存储子问题的解。确保状态数组的定义清晰明确能够正确地表示问题的状态。 初始化状态数组 在开始动态规划求解之前需要初始化状态数组的初始值。通常情况下初始状态是已知的可以根据问题的具体情况进行初始化。 状态转移方程的实现 根据问题的状态转移方程编写代码实现状态的转移。确保在状态转移过程中正确地更新状态数组的值。 处理边界情况 在动态规划问题中通常需要考虑边界情况如数组为空、字符串长度为0等特殊情况。确保在处理边界情况时能够正确处理避免出现错误。 当涉及到动态规划相关的场景题时以下是一些常见的总结和技巧 背包问题背包问题是动态规划中的经典问题之一。它包括0-1背包问题、完全背包问题和多重背包问题。在解决背包问题时需要定义状态和状态转移方程并使用二维数组或一维数组进行动态规划求解。 最长公共子序列LCSLCS问题是求解两个字符串中最长公共子序列的长度。可以使用二维数组进行动态规划求解定义状态和状态转移方程逐步填充数组并找到最长公共子序列。 最长递增子序列LISLIS问题是求解一个序列中最长递增子序列的长度。可以使用一维数组进行动态规划求解定义状态和状态转移方程逐步更新数组并找到最长递增子序列。 最大子数组和最大子数组和问题是求解一个数组中连续子数组的最大和。可以使用一维数组进行动态规划求解定义状态和状态转移方程逐步更新数组并找到最大子数组和。 最小路径和最小路径和问题是求解一个二维网格中从左上角到右下角的最小路径和。可以使用二维数组进行动态规划求解定义状态和状态转移方程逐步填充数组并找到最小路径和。 可以按照博主列的顺序由简至中等难度进行刷题 509. 斐波那契数
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1给定 n 请计算 F(n) 。 最简单的动态规划题目已经给了动态转移方程了套用即可 /*** param {number} n* return {number}*/
var fib function (n) {let dp [0];dp[1] 1;for (let i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n]
};
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 由题目可知一次可以爬一个或2个那么在第n层的时候我可能是从n-2层通过走两步上来也可能在n-1层走一步上来。所以状态转移方程d(n)d(n-2)d(n-1); 我只要知道走到n-2需要多少步走到n-1需要多少步。 由状态转移方程推到初始值d(1)1 d(2)2 当n3时进入转移方程求解 /*** param {number} n* return {number}*/
var climbStairs function (n) {//定义转移矩阵初始值const dp [0, 1, 2];for (let i 3; i n; i) {//根据题目推演的转移表达式dp[i] dp[i - 1] dp[i - 2];}return dp[n];
}; 746. 使用最小花费爬楼梯
数组的每个下标作为一个阶梯第 i 个阶梯对应着一个非负数的体力花费值 cost[i]下标从 0 开始。
每当爬上一个阶梯都要花费对应的体力值一旦支付了相应的体力值就可以选择向上爬一个阶梯或者爬两个阶梯。
请找出达到楼层顶部的最低花费。在开始时你可以选择从下标为 0 或 1 的元素作为初始阶梯。 思路这道题如果单独出现可能会多思考一下转移方程应该怎么写呢尤其是加上了花费花费cost[i]应该在计算当前dp[i]计算还是在后面计算 这里假设 i 就是阶梯顶你可以思考一下如果i是阶梯顶那么i的花费是不是可以不用计算了。你只用想前一步的花费和前两步的花费到达阶顶哪个最少不就好了。 因此第一种dp[i]dp[i-2]cost[i-2] 从倒数第二个台阶加上第二个台阶的花费跳两步到顶端 第二种dp[i]dp[i-1]cost[i-1]从倒数第一个台阶加上第一个台阶的花费跳一步到顶端 ok那么取两者的最小值即可这里n表示第几个台阶所以返回dp[n] /*** param {number[]} cost* return {number}*/
var minCostClimbingStairs function (cost) {let n cost.length;let dp [0, 0]for (let i 2; i n; i) {dp[i] Math.min(dp[i - 2] cost[i - 2], dp[i - 1] cost[i - 1]);}return dp[n];
};
198. 打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 思路还是看怎么推演出动态方程。 首先不用想太多题目给的不能相邻偷比如n表示数组下标n2时按示例1此时偷的金额可以是13也可以是2就这两种。 动态方程推演的时候跟递归类似你只需要考虑当前的结果前两步的结果。不用考虑前两步是怎么来的。 所以当下标为n时小偷能够偷的最多金额为dp(n)Math(dp[n-2]nums[n],dp[n-1])。从前两步跳的两种方式找个最大值。 然后由动态方程去推初始状态dp(0)nums[0]dp[1]Math(dp[0],dp[1])就好了 注意这里n表示的是数组下标 /*** param {number[]} nums* return {number}*/
var rob function (nums) {let n nums.length - 1;let dp [];dp[0] nums[0];if (n 1) {dp[1] Math.max(dp[0], nums[1]);}for (let i 2; i n; i) {dp[i] Math.max(dp[i - 2] nums[i], dp[i - 1]);}return dp[n];
}; 213. 打家劫舍 II
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 思路这题难点在于怎么避开首尾都选的情况。 我的思路是这样只考虑两种情况就是从哪个位置开始。如果选了第一个即nums[0]那么dp返回的值只取到dp[nums.length-2]倒数第二个的dp值因为最后一个值不能用。 如果选了第二个那么不用考虑首位是否相接因为第一个就不选。那么dp返回的值取dp[nums.length-1]。 比较两种情况的dp返回最大值即可。 /*** param {number[]} nums* return {number}*/
var rob function (nums) {if (nums.length 1) { return nums[0]; }//dp1第一个值必选最后的值不选返回最后一个前面的值//dp2第一个值不选后面的正常计算。let dp1 Array(nums.length).fill(0);let dp2 Array(nums.length).fill(0);dp1[0] nums[0];for (let i 1; i nums.length; i) {if (i 1) {dp1[1] dp1[0]; //dp1从第一个选dp2[1] nums[1]; //dp2从第二个开始选} else {dp1[i] Math.max(dp1[i - 2] nums[i], dp1[i - 1]);dp2[i] Math.max(dp2[i - 2] nums[i], dp2[i - 1]);}}// console.log(dp1 dp1);// console.log(dp2 dp2);return Math.max(dp1[nums.length - 2], dp2[nums.length - 1]);
}; dp1和dp2可以放在一起计算只不过返回的时候取出对应的值即可。打印dp组看下 118. 杨辉三角
给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。 动态规划-二维数组 老规矩先找规律观察最后一行吧两端为1第i行j列的结果第i-1行j-1列第i-1行j列 ok动态方程dp[i][j]dp[i-1][j-1]dp[i-1][j] 找i和j的边界值i从0到numRows-1; j从1到i-1。去掉两端的1 /*** param {number} numRows* return {number[][]}*/
var generate function (numRows) {//dp初始化let dp [];//双层循环 i表示层数j表示每层数组的长度for (let i 0; i numRows; i) {//第i行数组的长度为i1dp[i] new Array(i 1).fill(1);//第i行两端都为1所以j从1到i-1for (let j 1; j i; j) {//观察规律在j的范围内d[j]d[j-1]d[j]然后把二维数组前面的一维数组加上就行了dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];}}return dp;
}; 这里通过new Array(i1)创建了i1长度的数组并通过fill(1)方法填充数组得到一个i1长度的全1数组。dp[i][j]的值通过动态方程求解。 119. 杨辉三角 II
给定一个非负索引 rowIndex返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。 思路跟上面一样只不过rowIndex表示数组下标注意i的取值 然后返回的是某行的值不用返回全部但是动态方程还是二维的因为每个值的计算是二维的关系。 /*** param {number} rowIndex* return {number[]}*/
var getRow function (rowIndex) {let dp [];for (let i 0; i rowIndex; i) {dp[i] new Array(i 1).fill(1);for (let j 1; j i; j) {dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];}}return dp[rowIndex];
}; 121. 买卖股票的最佳时机
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 思路这个题目的动态方程不是那么直接首先需要一个max变量存储过程中最大的利润值。定义dp[i]表示第i天能够获得的最大利润。 dp[i]如果卖掉它能得到的最大利润dp[i]前一个最大利润当前-前一个的差值如果这个利润小与0当前卖掉为0。 所以动态方程为dp[i]Math.max(0,dp[i-1]prices[i]-prices[i-1]; 这里0可以通过初始化dp[i]为0得到 /*** param {number[]} prices* return {number}*/
var maxProfit function (prices) {let dp Array(prices.length).fill(0);let max 0;for (let i 1; i prices.length; i) {//dp[i]表示第i天卖股票能够获取的最大利润dp[i] Math.max(dp[i], dp[i - 1] prices[i] - prices[i - 1]);max Math.max(max, dp[i]);}return max;
}; 打印dp数组看下发现最大值在下标4位置当股票价格为6时卖出买入的价格为1在i4这天可以获得最大值。 122. 买卖股票的最佳时机 II 给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。 在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。 返回 你能获得的 最大 利润 。 思路 这里转换思想求第i天手里有多少现金。分两种情况第i天持有股票第i天不持有。用两个dp表示 dp1[i]表示第i天持有股票,手里的最大现金 dp2[i]表示第i天不持有股票手里的的最大现金 更新dp1数组 dp1数组分两种情况要么前一天持有要么前一天没持有今天买入 对于第一种情况如果i-1天持有i天的手里现金保持不变。dp1[i]dp[i-1]i-1天没持有第i天买入手里现金dp1[i]dp2[i-1]-prices[i] 更新dp2数组也分两种情况要么前一天没有要么前一天有今天卖掉 如果前一天不持有dp2[i-1]如果前一天持有第i天卖出dp2[i]dp1[i-1]prices[i] 为什么第i天卖出收益prices[i]因为你买的时候成本已经扣掉了加上卖的前正好是你的收入啊 /*** param {number[]} prices* return {number}*/
var maxProfit function (prices) {let dp1 Array(prices.length).fill(0);let dp2 Array(prices.length).fill(0);for (let i 1; i prices.length; i) {dp1[i] Math.max(dp1[i - 1], dp2[i - 1] - prices[i]);dp2[i] Math.max(dp2[i - 1], dp1[i - 1] prices[i]);}// console.log(dp1 dp1);// console.log(dp2 dp2);return dp2[prices.length - 1];
};
// 测试
const prices [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // 输出最大利润打印dp数组看下 dp1[i]表示第i天持有手里的现金最大值 dp2[i]表示第i天不持有手里现金最大值 5. 最长回文子串
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 思路从题解来看这道题总共有三种解法一种是暴力求解通过双指针移动找回文串在根据回文串返回最长的回文。第二种是中心扩散法枚举回文中心点包括奇数中心点和偶数中心点不断向两端扩散保存最长子串。第三种就是文章里使用的使用动态规划求解。 在做到这个题目的时候明细感觉上了难度从一维矩阵到二维矩阵了不画图很难理解了尤其是状态转移矩阵变得不好推断了。 来看一下官方题解给出的思路吧 如果一个字符串是回文串那么去掉首位两端它依然是个回文串见上图示例。 如果用i表示字符串左边indexj表示字符串右边index。dp[i][j]表示ij指向的字符串是否是回文。 那么一定有dp[i][j]dp[i-1][j-1]s[i]s[j] 怎么理解就是前面说的两端相等并且去掉两端里面的子串也是回文串那么当前i,j包围的序列也是回文。由此可知动态转移方程为 dp[i][j]dp[i-1][j-1]s[i]s[j] 特殊情况处理 如果s[i]s[j]此时j-i2那就有三种情况 bab 肯定是回文 bb 肯定是回文 b 也肯定是回文 因此总的转移矩阵关系 接下来看代码怎么写 由于i表示左侧j表示右侧那么j肯定大于i。所以填充的是矩阵的右上角。并且dp[i][j]要先知道dp[i1][j-1]的值所以要先计算矩阵左下角的值也就是按列计算而不是按行计算先计算第一列在计算第二列。。依次类推。到最后一列如下示例要直到dp[0][4]也就是整个串是不是回文由于s[0]s[4]所以看dp[1][3]是不是回文即可由矩阵推演dp[1][3]true所以dp[0][4]也为true。 /*** param {string} s* return {string}*/
var longestPalindrome function (s) {let n s.length;let maxLen 1, begin 0;let dp Array.from(Array(n), () Array(n).fill(false));for (let j 0; j n; j) {for (let i 0; i j; i) {if (s[i] s[j]) {if (j - i 2) {dp[i][j] true;} else {dp[i][j] dp[i 1][j - 1];}}if (dp[i][j] j - i 1 maxLen) {maxLen j - i 1;begin i;}}}return s.substring(begin, begin maxLen);
}; 只用记住需要改变maxLen时的i的位置即可不需要将每次的子串都保留 let dp Array.from(Array(n), () Array(n).fill(false)); 这行代码的作用是创建一个二维数组 dp用于记录子串是否为回文串的状态。让我们逐步解释这行代码的含义 Array(n)创建一个长度为 n 的一维数组其中每个元素的初始值为 undefined。Array.from()Array.from() 方法从一个类似数组或可迭代对象中创建一个新的数组实例。在这里我们将上一步创建的一维数组作为参数传递给 Array.from()。() Array(n).fill(false)这是 Array.from() 方法的第二个参数是一个箭头函数用于定义新数组中每个元素的值。在这里我们定义每个元素为一个长度为 n 的一维数组初始值为 false。最终dp 就是一个大小为 n x n 的二维数组用于记录子串是否为回文串的状态。例如dp[i][j] 表示从索引 i 到索引 j 的子串是否为回文串。 这种方式创建二维数组的方法在JavaScript中是比较常见的特别适用于动态规划等需要使用二维数组的场景。 53. 最大子数组和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。 思路这道题放在动态规划的分类里嗯感觉使用动态规划有点大材小用。可能用双指针比较多。既然用动态规划了那看下怎么解决吧。 这里没有要求返回最大和的下标所以用dp[i]表示当前的最大和包括当前如果前面计算的最大数组和是负数那么计算dp[i]s[i]。如果前面计算的是正数那么保留之前的子序列dp[i]dp[i-1]s[i]。并将过程中得到的序列最大值赋给max 最后返回的是dp数组中最大的值不是最后一项的值 /*** param {number[]} nums* return {number}*/
var maxSubArray function (nums) {let dp [];dp[0] nums[0];let max nums[0];for (let i 1; i nums.length; i) {dp[i] Math.max(dp[i - 1] nums[i], nums[i])max dp[i] max ? dp[i] : max;}return max;
}; 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径 思路路径问题的入门级简单题由于我先刷的64再来看这题感觉好简单秒了。由于题目让机器人只能向右或向下走所以第一列和第一行只有一种方式到达那就是一直向右走或一直向下走。 对与第m行第n列的位置机器人可能是从m行n-1列过来也可能是第m-1行第n列过来。因此动态转移方程为 dp[i][j] dp[i - 1][j] dp[i][j - 1]; /*** param {number} m* param {number} n* return {number}*/
var uniquePaths function (m, n) {let dp Array.from(Array(m), () Array(n).fill(1));for (let i 1; i m; i) {for (let j 1; j n; j) {dp[i][j] dp[i - 1][j] dp[i][j - 1];}}return dp[m - 1][n - 1];
}; 由于第一行和第一列都是只有一种方式所以在初始化的时候用全部为1好了这样处理其他的元素就好啦 63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径网格中的障碍物和空位置分别用 1 和 0 来表示。 思路这道题的边界真的。。这个障碍会出现在任何角落任何包括入口包括出口 提交的时候才知道 老样子dp[i][j]表示第i行第j列路径个数。那么dp[i][j] dp[i - 1][j] dp[i][j - 1];不一样的是如果路径有障碍dp[i][j]0不用参与计算。这道题的主体容易复杂的是边界值处理。首先还是初始化m*n列填充为1的数组这样避免了处理首行和首列的边界。根据obstacleGrid障碍数据提供的1值将dp[i][j]相应的设为0。这里边界要特殊处理因为首行只有前面有一个障碍后面全为0全走不通。同理首列只要上面有一个障碍后面的都走不通。 这题也不算难就是边界要慢慢处理 /*** param {number[][]} obstacleGrid* return {number}*/
var uniquePathsWithObstacles function (obstacleGrid) {let m obstacleGrid.length;let n obstacleGrid[0].length;//初始化二维数组全部为1,避免在处理第0行和第0列的情况了let dp Array.from(Array(m), () Array(n).fill(1));//遍历所有的数据找到阻碍将其设置0for (let i 0; i m; i) {for (let j 0; j n; j) {if (obstacleGrid[i][j] 1) {dp[i][j] 0;}}}//处理边界第0列dp[i][0]必须同时满足当前是1并且前一行也是1for (let i 1; i m; i) {dp[i][0] dp[i][0] dp[i - 1][0] ? 1 : 0;}//处理边界第0行dp[0][j]必须同时满足当前是1并且前一列也是1for (let j 1; j n; j) {dp[0][j] dp[0][j] dp[0][j - 1] ? 1 : 0;}//从其他元素进行dp算法由于某个路径可能有障碍所以不是无脑的跳哦有可能只能从左边过来也有可能只能从上面过来for (let i 1; i m; i) {for (let j 1; j n; j) {if (dp[i][j] ! 0) {//计算路径和dp[i][j] dp[i - 1][j] dp[i][j - 1];}}}return dp[m - 1][n - 1];
}; 64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步。 思路这道题就是爬楼梯的变形吗从走一步或两步变成只能向右或向下走。面临这种选择性的问题的时候动态规划就出来了。先看能否得到转移方程。这个题目还是比较好理解的。直接看矩阵的右下角这里放个矩阵。假如要计算amn的最小值那它只有两种结果要么从am-1n向下走一步要么从amn-1向右走一步。因此得到转移矩阵 dp[m][n]Math.min(dp[m-1][n],dp[m][n-1])grid[m][n]。 转移矩阵得到了这个时候要考虑边界值可以发现矩阵的第一行和第一列是只能通过向右或向下得到。所以要单独处理不能使用动态转移方程。因此可以得到如下代码 /*** param {number[][]} grid* return {number}*/
var minPathSum function (grid) {let m grid.length;let n grid[0].length;//创建一个m*n的二维数组let dp Array.from(Array(m), () Array(n).fill(0));//初始值左上角单独赋值dp[0][0] grid[0][0];//第0列单独赋值只能一直向下走dp[i][0],i从1到m-1for (let i 1; i m; i) {dp[i][0] dp[i - 1][0] grid[i][0];}//第0行单独赋值只能一直向右走dp[0][j],j从1到n-1列for (let j 1; j n; j) {dp[0][j] dp[0][j - 1] grid[0][j];}//动态规划方程dp[i][j]可以由相同列的前面一行过来也可以由相同行的左边一列过来两者取最小for (let i 1; i m; i) {for (j 1; j n; j) {dp[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];}}return dp[m - 1][n - 1];
};
674. 最长连续递增序列
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。 思路求最长连续递增序列。先想一下动态规划dp[i]表示什么意思 这里定义dp[i]表示从前i个字符中与当前i能够匹配的最大连续递增字符串的长度也就是第i个元素时最长递增字符的最后一个。如果第i个元素大于i-1那么递归公式 dp[i-1]1 在这个过程中保留最大值即可。 比如下面示例在i6即dp[i]101时下标4-6组成了长度为3的递增序列。 /*** param {number[]} nums* return {number}*/
var findLengthOfLCIS function (nums) {let dp Array(nums.length).fill(1);let max 1;//dp[i]表示长度为i的子串中连续递增子序列的最大长度for (let i 1; i nums.length; i) {if (nums[i] nums[i - 1]) {dp[i] dp[i - 1] 1;max Math.max(max, dp[i]);}}// console.log(dp dp);return max;
};
300. 最长递增子序列
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组[0,3,1,6,2,2,7] 的子序列。 思路使用动态规划动态更新最长递增子序列长度。这里dp[i]表示长度为i的字符串其最长子序列的长度。怎么初始化由于递增子序列至少为1就是元素都是降序排列的每个子串最少就是它当前只有一个元素。 这里在求子序列肯定要用到左指针进行移动不然你怎么左右夹击找到子串。所以是两层for循环。 外循环i从1到nums.length-1表示子串的数量逐步增加。每趟循环只能确定dp[i]的值 内循环j从0到i代表左指针每次从子串的最左边开始向右靠近。以nums[i]作为基准值如果左边元素dp[j]小与基准值则1dp[j]的长度与dp[i]的长度进行比较取最大值。否则不用加入子序列长度。j向右移动一位在计算左侧与基准值比较的结果。 用dp数组打印的结果看下每趟循环i后dp数组的变化变容易理解了。 打印dp数组可以发现在i3即nums[i]5时开始有了子序列长度1
代码如下
/*** param {number[]} nums* return {number}*/
var lengthOfLIS function (nums) {if (!nums.length) return 0;let dp Array(nums.length).fill(1);let max 1;//dp[i]长度为i的子串中最长递增子序列的长度for (let i 1; i nums.length; i) {for (let j 0; j i; j) {if (nums[j] nums[i]) {dp[i] Math.max(dp[i], 1 dp[j]);}}// console.log(i, i, dp , dp);max Math.max(max, dp[i]);}// console.log(dp dp);return max;
}; 背包问题
背包问题指的是将一堆物品放进背包背包的容量是一定的。但根据物品的重量、体积、每个物品的个数不同背包问题演化为装满背包的最大价值、装满背包需要多少种组合等。
对于其他问题如零钱兑换为题可以转换为使用背包的思想来解决。比如可以用背包的容量模拟你想达到的个数待装进背包的物品模拟你可以使用的硬币用多少硬币凑成一个总数就转换为用多少物品装满背包。
理解背包问题除了掌握递推公式dp[n]的推导对于组合问题还需要了解先遍历物品还是先遍历背包。掌握了相关的场景就算题型变换莫测也能有正确的思路。 我的解题思路 先求解背包的容量有些题目没有明显给出背包容量需要转化找出背包容量target。确定为背包问题。确定dp[target]状态转移方程是组合还是最大最小值。通常组合运用dp[j]dp[j-num[i]]这种形式最大值dp[j]Math.max(dp[j],dp[j-num[i]])num[i]/1这种。在看dp[0]的初始化是0还是1。一般来说对于有多少种组合dp[0]1其他dp[0]0;然后看两层for循环是先循环背包容量还是物品种类。对于一维dp数组这里有个固定的模板如果每个物品只有一个那么是01背包那就是物品优先外循环物品内循环背包容量且背包容量从大到小。如果物品数量多个是完全背包for循环顺序可以任意先循环物品和先循环背包结果一样但都要从小到大。看输出一般是dp[target]的值。但如果输出true或false需要将组合数判断一下一般初始化都为0如果没找到最后也为0为0表示false。 常说的0-1背包是什么 0-1背包指的是每个物品数量只有一个 完全背包值得是每种类别的物品有很多个。 背包递推公式
1.问能否能装满背包或者最多装多少 dp[j] max(dp[j], dp[j - nums[i]] nums[i]); 2.问装满背包有几种方法 dp[j] dp[j - nums[i]] 3.问背包装满最大价值 dp[j] max(dp[j], dp[j - weight[i]] value[i]); 4.问装满背包所有物品的最小个数 dp[j] min(dp[j - coins[i]] 1, dp[j]); dp[0]如何初始化
1.对于组合问题比如有多少种组合dp[0]1 dp[0]一定要为1dp[0] 1是 递归公式的基础。如果dp[0] 0 的话后面所有推导出来的值都是0了。那么 dp[0] 1 有没有含义其实既可以说 凑成总金额0的货币组合数为1也可以说 凑成总金额0的货币组合数为0好像都没有毛病。 2.对于其他如求总价值dp[0]
0-1背包
先遍历物品还是背包容量
背包问题中使用哪种循环至关重要
外层for循环遍历物品钱币内层for遍历背包金钱总额外层for遍历背包金钱总额内层for循环遍历物品钱币 这里直接给出结论如果是01背包并且你用的是一维数组表示。那么先遍历物品在遍历背包容量。并且背包容量从大到小进行遍历。 即 for(let 物品 of 物品数组){ for(let i target目标容量i物品i--){ } } 这个顺序是固定的调换for循环顺序或者内循环遍历方式改变都不行。 那为什么要先遍历物品呢 从dp的推导发现的如果先遍历容量那么某个物品会重复加入而01背包中物品的个数只有一个。所以要写遍历物品。 为什么遍历背包容量时要从大到小呢 也是从dp的推导发现如果从小到大后面的会受前面的影响也会重复计算物品。 由于使用了一维数组dp[j]在遍历时会多次滚动参与计算。不像二维数组遍历后就确定了。所以循环的顺序很重要 举例518零钱兑换这题要求凑成总金额的不同硬币组合。
for (let i 0; i coins.length; i) { // 遍历物品for (let j coins[i]; j amount; j) { // 遍历背包容量dp[j] dp[j - coins[i]];}
}
假设coins[0] 1coins[1] 5。
那么就是先把1加入计算然后再把5加入计算得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数这才是本题需要的 所以按照物品优先的顺序1,5是物品出现的顺序那就算一次对于5,1不能重复计算 如果把两个for交换顺序代码如下
for (let j 0; j amount; j) { // 遍历背包容量for (let i 0; i coins.length; i) { // 遍历物品if (j - coins[i] 0) dp[j] dp[j - coins[i]];}
}
背包容量的每一个值都是经过 1 和 5 的计算包含了{1, 5} 和 {5, 1}两种情况。此时dp[j]里算出来的就是排列数不是我们想要的 倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品i就会被重复加入多次 如果每种物品只有一个即0-1背包问题那么在第二层循环遍历背包容量时要从大到小 416.分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 思路先看怎么转换为背包问题。从题目可知分割后两个子集和相等。所以sum求和后肯定是偶数。然后可以转换为从nums数组中找出能够凑成sum/2的个数。ok背包问题的target找到了。定义dpdp[j]表示装满背包容量为j有几种方式。然后看先循环背包还是物品分析题目这里物品数量只有一个所以是01背包。先循环物品并且内循环从大到小每次先更新大的dp。最后输出问题如果dp[target]0说明可以找到组合。 /*** param {number[]} nums* return {boolean}*/
var canPartition function (nums) {//可以分割为两个相等子集说明sum是可以被2整除的let sum nums.reduce((pre, num) pre num, 0);if (sum % 2 ! 0) return false;//目标转而求从nums数组中找到可以构成sum/2的个数这里顺序不同也是同一个所以外循环物品优先let target sum / 2;let dp Array(target 1).fill(0);dp[0] 1;for (let i 0; i nums.length; i) {//先遍历物品在遍历容量for (let j target; j nums[i]; j--) {//由于物品只有一个所以内循环由大到小dp[j] dp[j - nums[i]];}}return dp[target] 0;
}; 1049.最后一块石头的重量 II 有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。 思路这是「从序列中选择子序列使得和接近target」系列的题目 先看背包问题的target。可以将石头的重量看作是物品的重量然后尝试将这些物品放入一个背包中使得背包的重量尽可能接近总重量的一半。最终剩下的石头的重量就是背包中物品的总重量减去背包的重量。可以理解为背包容量为totalSum/2时能够装的最大的重量是多少。确定dp[i]含义dp[i]表示背包容量为i时能够容量的最大重量。再看先循环物品还是背包由于物品只有一个并且一维数组先循环物品并且内循环背包容量从大到小。确定递推关系dp[j]定义为容量为j时能够装的下的物品最大重量。因此第j个物品选和不选时取一个最大值 dp[j]Math.max(dp[j],dp[j-stones[i]]stones[i]]); 在看输出分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum - dp[target]。 在计算target的时候target sum / 2 因为是向下取整所以sum - dp[target] 一定是大于等于dp[target]的。那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。 /*** param {number[]} stones* return {number}*/
var lastStoneWeightII function (stones) {//将石头的重量看作是物品的重量然后尝试将这些物品放入一个背包中使得背包的重量尽可能接近总重量的一半。const totalSum stones.reduce((pre, num) pre num, 0);const target Math.floor(totalSum / 2);let dp Array(target 1).fill(0);for (let i 0; i stones.length; i) {for (let j target; j stones[i]; j--) {dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);//dp[j] 表示在背包容量为 j 的情况下可以达到的最大重量}}return totalSum - 2 * dp[target];
};
dp[j] 表示在背包容量为 j 的情况下可以达到的最大重量。换句话说dp[j] 存储的是在背包容量为 j 时可以放入的石头的最大总重量。
在动态规划的过程中我们不断更新 dp 数组的值使得 dp[j] 表示在背包容量为 j 时的最优解。通过不断更新 dp 数组最终可以得到在背包容量为 target总重量的一半时的最大重量然后通过计算 totalSum - 2 * dp[target]得到剩下的石头的最小可能重量。
494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 思路先看怎么转换为背包问题。从这题来看这是需要先推理看能否找到背包容量。 这里nums所有的值都参与计算可以将集合写成加正号的集合P和负数的集合N这里不加符号则PNsum (sum是 nums的集合累加和)。 而题目要求P-Ntarget,高中都学过上下两式子相加可得Psumtarget/2 因此可将题目从求target变成从nums找能够凑成P的个数。OK背包容量找到了。 确定dp[target]含义:填满target包括j这么大容积的包有多少种方法。 然后看先循环背包还是物品确定01背包老套路先循环物品在循环背包容量背包容量由大到小。 观察PP表示正数部分和因此P0并且sumtarget必须为偶数 如果为奇数P就带小数点了而nums[i]都是正整数 /*** param {number[]} nums* param {number} target* return {number}*/
var findTargetSumWays function (nums, target) {//nums所有值都参与计算可以将集合写成加正号的集合P和加负数的集合N则PNSUM sum是 nums的集合累加和。//而题目要求P-Ntarget,可得正数部分Psumtarget/2 因此可将题目从求target变成从nums找能够凑成P的个数//观察PP表示正数部分和因此P0并且sumtarget必须为偶数let sum nums.reduce((a, b) a b, 0);if ((sum target) % 2 ! 0 || (sum target) 0) {return 0;}let targetSum (sum target) / 2;let dp Array(targetSum 1).fill(0);dp[0] 1;//枚举正数项凑成target// dp[i]表示凑成target的个数for (let num of nums) {//枚举正数相当与枚举背包中的物品重量for (let i targetSum; i num; i--) {//相当与枚举背包剩余容量dp[i] dp[i - num];}}return dp[targetSum];}; 因此本题在于背包容量为(sumtarget)/2时从nums[i]里能够有多少种这里相同的元素但是下标不同也代表不同的物品。 474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素集合 x 是集合 y 的 子集 。 思路这个背包有两个维度一个是m 一个是n而不同长度的字符串就是不同大小的待装物品。一维数组无法满足所以需要一个二维数组表示。用dp[i][j]表示最多有i个0和j个1的strs的最大子集的大小。 先遍历物品在遍历背包背包容量从大到小。 /*** param {string[]} strs* param {number} m* param {number} n* return {number}*/
var findMaxForm function (strs, m, n) {let dp Array.from(Array(m 1), () Array(n 1).fill(0));let numOfZeros, numOfOnes;for (let str of strs) {//外层遍历物品numOfZeros countZeros(str);numOfOnes str.length - numOfZeros;for (let i m; i numOfZeros; i--) {//内层遍历背包容量容量从大到小遍历for (let j n; j numOfOnes; j--) {//双层循环上下顺序随意dp[i][j] Math.max(dp[i][j], dp[i - numOfZeros][j - numOfOnes] 1);//当前物品选或不选取最大值}}}return dp[m][n];
};
function countZeros(str) {let count 0;for (let s of str) {if (s 0) {count;}}return count;
}
完全背包
先遍历物品还是背包容量 背包问题中使用哪种循环至关重要 外层for循环遍历物品钱币内层for遍历背包金钱总额外层for遍历背包金钱总额内层for循环遍历物品钱币 322.零钱兑换
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。你可以认为每种硬币的数量是无限的。 思路这道题建议直接先去题解。有人说是背包问题有人说是爬楼梯变形。按照爬楼梯的思路去解释一下。假设dp[i]表示凑成金额i需要的最小硬币数然后把硬币种类换成爬楼梯的方式比如示例中硬币种类1、2、5那么dp[i]可以通过dp[i-1]或dp[i-2]或dp[i-5]方式凑得所以动态方程来了 dp[i]Math.min(dp[i-coins[0],dp[i-coins[1]],dp[i-coins[j])1 1表示可以匹配上 /*** param {number[]} coins* param {number} amount* return {number}*/
var coinChange function (coins, amount) {let Max amount 1;let dp Array(amount 1).fill(Max);dp[0] 0;for (let i 1; i amount; i) {for (let j 0; j coins.length; j) {if (coins[j] i) {dp[i] Math.min(dp[i], dp[i - coins[j]] 1);}}}return dp[amount] amount ? -1 : dp[amount]
}; 定义一个一维数组 dp其中 dp[i] 表示凑成金额 i 所需的最少硬币个数。初始时将 dp 数组填充为一个较大的值表示无法凑成对应金额。然后我们遍历每个金额尝试用每种硬币去凑成该金额并更新 dp 数组的值。最终dp[amount] 就是所需的最少硬币个数。如果无法凑成总金额则返回 - 518. 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 思路先看怎么转换为背包问题。从题目来看这就是一个纯背包问题amount就是背包的容量。coins是物品种类每种物品不限数量因此是完全背包。然后看先循环背包还是物品分析题目这里组合与顺序无关所以是物品优先外循环是物品内循环是背包。OK这里内外循环搞定。再看内循环是背包容量从小到大还是从大到小。由题目可知这是完全背包物品容量应该有小到大每次先更新容量小的dp。最后输出问题可以根据dp[target]0转成布尔类型输出。 /*** param {number} amount* param {number[]} coins* return {number}*/
var change function (amount, coins) {let dp Array(amount 1).fill(0);dp[0] 1;//背包问题初始化//强调组合数相同组合不同排列顺序仍为同一个先遍历物品for (let i 0; i coins.length; i) {//遍历物品for (let j coins[i]; j amount; j) {//遍历容量j从coins[i]开始dp[j] dp[j - coins[i]];//j-coins[i]肯定大于0}}return dp[amount];
};
377.组合综合IV
给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。 思路根据题目确定是背包问题。然后看先循环背包还是物品。有题目可知物品出现的顺序影像排列结果所以不是物品优先。外循环遍历背包容量内循环遍历物品种类。要判断i-nums[j]0这样才可以放入背包中计算dp。 /*** param {number[]} nums* param {number} target* return {number}*/
var combinationSum4 function (nums, target) {let dp Array(target 1).fill(0);dp[0]1;for (let i 1; i target; i) {for (let j 0; j nums.length; j) {if (i nums[j]) {dp[i] dp[i - nums[j]];}}}return dp[target];
};
279. 完全平方数
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 思路完全背包求最小组合数。背包容量是n物品是j物品能够放进背包的前提是j*ji。 求组合数dp[0]0这题先遍历背包还是物品都可但在完全背包里习惯先遍历背包。 定义dp[i]表示背包容量为i时能够装满的最少物品数量。那么递推公式 dp[i]Math.min(dp[i],dp[i-j*j]1)表示不放物品j时的组合数与放入物品j的组合数取最小值。 涉及取最小值出0外其他元素要初始为一个较大的数只有这样在覆盖时不会受初始值影响。 /*** param {number} n* return {number}*/
var numSquares function (n) {//背包是n 物品是j,j从0到n/2吧let dp Array(n 1).fill(Infinity);dp[0] 0;//dp[i]背包容量为i时装满的j的最少数量for (let i 1; i n; i) {for (let j 1; j * j i; j) {dp[i] Math.min(dp[i], dp[i - j * j] 1);}}// console.log(dp);return dp[n];
}; 这里打印dp数组看下。 比如n12从dp[0]到dp[12]打印如下。 [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3] 1有1组成 dp[2]11 2个 dp[3]111 3个 dp[4]2 1个 dp[5]21 2个 dp[6]211 3个 ... dp[12]444 3个 139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 思路这道题难点是如何找到背包。 可以将目标s看做背包wordDict看做物品。装满s并且考虑放入物品的顺序。 假设i-wordDict[j].length前的子串可以由wordDict组合得到那么我只需要判断wordDict[j]放进去还能不能凑成需要的子串即可。 使用dp[i]表示对于字符串s从[o,i)个下标中左闭右开截取的子串是否可以由wordDict拼接而成。 这里可以使用slice(a,b)截取子串。用leftIndex表示子串截取时左侧的位置i表示当前的位置。dp[i]为true的条件时未加入子串时dp[leftIndex]为true并且当前加入从s中截取的剩余字符串。 /*** param {string} s* param {string[]} wordDict* return {boolean}*/
var wordBreak function (s, wordDict) {let dp Array(s.length 1).fill(false);//dp初始化为length1是由slice特性决定截取子串时不包括当前元素dp[0] true;//必须初始化为true用于第一个字符串的匹配for (let i 0; i s.length; i) {//先遍历背包for (let j 0; j wordDict.length; j) {//在遍历物品let leftIndex i - wordDict[j].length;//wordDict[j].length表示物品的重量if (leftIndex 0) {if (s.slice(leftIndex, i) wordDict[j] dp[leftIndex]) {//dp[left]为true并且left和i中间的字符刚好和j匹配上dp[i] true;//表示0-i个字符串可以由wordDict中的字符串表示}}}}return dp[s.length];
}; 为什么返回的是dp[s.length]而不是dp[s.length-1]?
s leetcode
wordDict [leet,code] 使用上述示例进行调试可以发现当i为4即i指向字符c时wordDict的第一个字符串刚好可以匹配s.slice(leftIndex,i)‘leet’。为什么dp[4]为true这是由于slice截取字符串时不包含4的下标只截取到0,1,2,3。所以我们要知道s.length能不能由wordDict构成需要知道dp[s.length]是否为true。即dp[8]true。
