leetcode刷题（javaScript）——动态规划相关场景题总结
动态规划在 JavaScript 刷题中有一定的难度，但也是非常常见和重要的算法思想。动态规划通常适用于需要求解最优解、最大值、最小值等问题的场景，可以将复杂问题拆分成子问题，通过存储子问题的解来避免重复计算，从而提高效率。
理解问题的状态转移方程： 动态规划的核心是找到问题的状态转移方程，即如何从子问题的解推导出更大规模问题的解。理解问题的状态转移方程是解决动态规划问题的关键。
定义合适的状态数组： 在解决动态规划问题时，通常需要定义一个状态数组来存储子问题的解。确保状态数组的定义清晰明确，能够正确地表示问题的状态。
初始化状态数组： 在开始动态规划求解之前，需要初始化状态数组的初始值。通常情况下，初始状态是已知的，可以根据问题的具体情况进行初始化。
状态转移方程的实现： 根据问题的状态转移方程，编写代码实现状态的转移。确保在状态转移过程中正确地更新状态数组的值。
处理边界情况： 在动态规划问题中，通常需要考虑边界情况，如数组为空、字符串长度为0等特殊情况。确保在处理边界情况时能够正确处理，避免出现错误。
当涉及到动态规划相关的场景题时，以下是一些常见的总结和技巧：
-
背包问题：背包问题是动态规划中的经典问题之一。它包括0-1背包问题、完全背包问题和多重背包问题。在解决背包问题时，需要定义状态和状态转移方程，并使用二维数组或一维数组进行动态规划求解。
-
最长公共子序列（LCS）：LCS问题是求解两个字符串中最长公共子序列的长度。可以使用二维数组进行动态规划求解，定义状态和状态转移方程，逐步填充数组并找到最长公共子序列。
-
最长递增子序列（LIS）：LIS问题是求解一个序列中最长递增子序列的长度。可以使用一维数组进行动态规划求解，定义状态和状态转移方程，逐步更新数组并找到最长递增子序列。
-
最大子数组和：最大子数组和问题是求解一个数组中连续子数组的最大和。可以使用一维数组进行动态规划求解，定义状态和状态转移方程，逐步更新数组并找到最大子数组和。
-
最小路径和：最小路径和问题是求解一个二维网格中从左上角到右下角的最小路径和。可以使用二维数组进行动态规划求解，定义状态和状态转移方程，逐步填充数组并找到最小路径和。
可以按照博主列的顺序由简至中等难度进行刷题
509. 斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(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
当n>=3时进入转移方程求解
/**
* @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表示数组下标，n=2时，按示例1，此时偷的金额可以是1+3，也可以是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行数组的长度为i+1
dp[i] = new Array(i + 1).fill(1);
//第i行两端都为1，所以j从1到i-1
for (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(i+1)创建了i+1长度的数组，并通过fill(1)方法填充数组，得到一个i+1长度的全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，在i=4这天可以获得最大值。
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表示字符串左边index，j表示字符串右边index。dp[i][j]表示i，j指向的字符串是否是回文。
那么一定有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-i<=2，那就有三种情况
bab 肯定是回文
bb 肯定是回文
b 也肯定是回文
因此：总的转移矩阵关系
接下来看代码怎么写？
由于i表示左侧，j表示右侧，那么j肯定大于i。所以填充的是矩阵的右上角。并且dp[i][j]要先知道dp[i+1][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));
//遍历所有的数据，找到阻碍将其设置0
for (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并且前一行也是1
for (let i = 1; i < m; i++) {
dp[i][0] = dp[i][0] && dp[i - 1][0] ? 1 : 0;
}
//处理边界第0行，dp[0][j]必须同时满足，当前是1并且前一列也是1
for (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-1
for (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 和 r（l < 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
在这个过程中保留最大值即可。
比如下面示例在i=6，即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]小与基准值，则1+dp[j]的长度与dp[i]的长度进行比较，取最大值。否则不用加入子序列长度。j向右移动一位，在计算左侧与基准值比较的结果。
用dp数组打印的结果看下每趟循环i后，dp数组的变化变容易理解了。
打印dp数组，可以发现，在i=3，即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]一定要为1，dp[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] = 1，coins[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找到了。定义dp：dp[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（这里不加符号），则P+N=sum (sum是 nums的集合累加和)。
而题目要求P+（-N）=target,高中都学过，上下两式子相加可得P=（sum+target）/2因此，可将题目从求target变成从nums找能够凑成P的个数。OK背包容量找到了。
确定dp[target]含义:填满target（包括j）这么大容积的包，有多少种方法。
然后看先循环背包还是物品，确定01背包，老套路，先循环物品在循环背包容量，背包容量由大到小。
观察P，P表示正数部分和，因此P>0，并且sum+target必须为偶数 ，如果为奇数，P就带小数点了，而nums[i]都是正整数！
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function (nums, target) {
//nums所有值都参与计算，可以将集合写成加正号的集合P和加负数的集合N，则P+N=SUM sum是 nums的集合累加和。
//而题目要求P+（-N）=target,可得正数部分P=（sum+target）/2 因此，可将题目从求target变成从nums找能够凑成P的个数
//观察P，P表示正数部分和，因此P>0，并且sum+target必须为偶数
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];
};因此，本题在于背包容量为(sum+target)/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*j<=i。
求组合数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数组看下。 比如n=12，从dp[0]到dp[12]打印如下。
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]1有1组成
dp[2]=1+1 2个
dp[3]=1+1+1 3个
dp[4]=2 1个
dp[5]=2+1 2个
dp[6]=2+1+1 3个
...
dp[12]=4+4+4 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初始化为length+1是由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。
