动态规划

​ 动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

​ 做动规的题目，写代码之前一定要把状态转移在dp数组上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

动态规划的步骤：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

斐波那契数

描述：

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。

示例：

示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

思路：

1. 确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2. 确定递推公式

题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3. dp数组如何初始化

​ dp[0] = 0; dp[1] = 1;

4. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5. 举例推导dp数组

解法：

var fib = function(n){
    let dp = [0, 1];
    for(let i=2;i<=n;i++)
        dp[i] = dp[i-1]+dp[i-2];
    return dp[n];
}

爬楼梯

描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例：

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

思路：

dp[i] = dp[i-1]+dp[i-2]

解法：

var climbStairs = function(n){
    let dp = [1, 2];
    for(let i=2;i<n;i++)
        dp[i] = dp[i-1]+dp[i-2];
    return dp[n-1];
}

使用最小花费爬楼梯

描述：

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例：

示例 1：
输入：cost = [10, 15, 20] 
输出：15 
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

思路：

dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])

dp[0]=0, dp[1]=0;

解法：

var minCostClimbingStairs = function(cost){
    let 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];
}

不同路径

描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例：

示例 1：
输入：m = 2, n = 3
输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右

示例 2：
输入：m = 7, n = 3
输出：28

思路：

机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。

按照动规五部曲来分析：

1. 确定dp数组（dp table）以及下标的含义

dp[i] [j]：表示从（0 ，0）出发，到(i, j) 有dp[i] [j]条不同的路径。

2. 确定递推公式

想要求dp[i] [j]，只能有两个方向来推导出来，即dp[i - 1] [j] 和 dp[i] [j - 1]。

此时在回顾一下 dp[i - 1] [j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i] [j - 1]同理。

那么很自然，dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]，因为dp[i] [j]只有这两个方向过来。

3. dp数组的初始化

如何初始化呢，首先dp[i] [0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0] [j]也同理。

所以初始化代码为：

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

4. 确定遍历顺序

这里要看一下递推公式dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]，dp[i] [j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp[i] [j]的时候，dp[i - 1] [j] 和 dp[i] [j - 1]一定是有数值的。

5. 举例推导dp数组

解法：

var uniquePaths = function(m, n){
    // 创建数组与dp初始化同步进行
    // 数组初始值为1
    let dp = new Array(m).fill([]).map(()=>new 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];
}

矩阵的最小路径和

描述：

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

示例：

输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
返回值：12

解法：

function minPathSum( matrix ) {
    let row = matrix.length, col = matrix[0].length;
    let dp = new Array(row).fill([]).map(()=>new Array(col));
    dp[0][0]=matrix[0][0];
    // 初始化第一行
    for(let i=1;i<col;i++)
        dp[0][i]=dp[0][i-1]+matrix[0][i];
    // 初始化第一列
    for(let i=1;i<row;i++)
        dp[i][0]=dp[i-1][0]+matrix[i][0];
    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])+matrix[i][j];
    return dp[row-1][col-1];
}

不同路径II

描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

示例：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2 解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右

思路：

​ (i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。

​ 这个题的易错点有两个：

• 设置初始值的时候，行列中只要有任意一个是障碍物，那这个障碍物后续的格子都无法到达。且数组初始值为0。
• dp的时候，如果碰到障碍物那么当前格子就应该设置为0，否则使用公式

解法：

var uniquePathsWithObstacles = function(obstacleGrid){
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = new Array(m).fill([]).map(()=>new Array(n).fill(0));
    // for循环判断这里简直是太妙了！！！
    for(let i=0;i<m&&obstacleGrid[i][0]===0;i++)
        dp[i][0] = 1;
    for(let i=0;i<n&&obstacleGrid[0][i]===0;i++)
        dp[0][i] = 1;
    for(let i=1;i<m;i++)
        for(let j=1;j<n;j++)
            if(obstacleGrid[i][j]===0)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            else
                dp[i][j]=0;
    return dp[m-1][n-1];
}

整数拆分

描述：

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例：

示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

思路：

dp[i]：拆分数字i，可以得到的最大乘积为dp[i]。

有两种渠道得到dp[i]。一个是j * (i - j) 直接相乘。一个是j * dp[i - j]，相当于是拆分(i - j)。

dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

在取最大值的时候，为什么还要比较dp[i]呢？

因为在j循环中，每次dp[i]都会改变，需要记录dp[i]的最大值。

解法：

var intergerBreak = function(n){
    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++)
            dp[i] = Math.max(dp[i], (i-j)*j, j*dp[i-j]);
    return dp[n];
}

不同的二叉搜索树

描述：

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例：

思路：

**dp[i] ： 1到i节点组成的二叉搜索树的个数为dp[i]**。

dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

dp[i] += dp[j - 1] * dp[i - j]; j-1 为以j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

解法：

var numTrees = function(n){
    let dp = new Array(n+1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for(let i=2;i<=n;i++)
        // 此处j可以等于i，因为有子树有0个元素的情况
        for(let j=1;j<=i;j++)
            dp[i]+=dp[j-1]*dp[i-j];
    return dp[n];
}

背包问题基础

只需要掌握01背包和完全背包即可

01背包问题—二维数组

描述：

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

思路：

dp[i] [j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

解法：

var testWeightBagProblem = function(weight, value, size){
    const len = weight.length;
    const dp = new Array(len).fill([]).map(()=>new Array(size+1).fill(0));
    for(let i=weight[0];i<=size;i++)
        dp[0][i] = value[0];
    for(let i=1;i<len;i++)
        for(let j=0;j<=size;j++)
            if(j<weight[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
    return dp[len-1][size];        
} 

01背包问题—一维数组

需要满足的条件是上一层可以重复利用，直接拷贝到当前层

思路：

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

遍历顺序：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { 
        // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

​ 二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

​ 代码中不可以先遍历背包容量嵌套遍历物品。因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

解法：

var testWeightBagProblem = function(weight, value, size){
    const len = weight.length;
    const dp = new Array(size+1).fill(0);
    for(let i=0;i<len;i++)
        for(let j=size;j>=weight[i];j--)
            // 因为一维数组的解法是基于覆盖的思路，所以max里面这个dp[j]实际就是上一轮的结果
            dp[j] = Math.max(dp[j], value[i]+dp[j-weight[i]]);
    return dp[size];
}

分割等和子集

描述：

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100,数组的大小不会超过 200

示例：

示例 1: 
输入: [1, 5, 11, 5] 
输出: true 
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2: 
输入: [1, 2, 3, 5] 
输出: false 
解释: 数组不能分割成两个元素和相等的子集.

思路：

​ 元素只能使用一次，故是01背包问题。

只有确定了如下四点，才能把01背包问题套到本题上来。

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

​ 本题中，**dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]**。递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

​ 如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

解法：

var canPartition = function(nums){
    const sum = nums.reduce((a,b)=>a+b);
    const dp = new Array(sum/2+1).fill(0);
    // 如果是奇数则不可能分成两个相等的子集
    if(sum%2===1)
        return false;
    for(let i=0;i<nums.length;i++)
        for(let j=sum/2;j>=nums[i];j--)
            dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
    return dp[sum/2]===sum/2;
}

最后一块石头的重量II

描述：

有一堆石头，每块石头的重量都是正整数。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000

示例：

输入：[2,7,4,1,8,1] 
输出：1 
解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

思路：

​ 本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

​ dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。

​ dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

​ 因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。

解法：

var lastStoneWeightII = function(stones){
    let sum = stones.reduce((a,b)=>a+b);
    let target = Math.floor(sum/2);
    let dp = new 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[target]表示这一部分能装的最大重量
    // 那么sum-dp[target]就是另一部分的重量
    return (sum-dp[target])-dp[target];
}

目标和

描述：

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。

思路：

​ 结果为target，那么就一定有 left组合 - right组合 = target。left + right等于sum，而sum是固定的。于是有： left - (sum - left) = target -> left = (target + sum)/2 。target是固定的，sum是固定的，left就可以求出来。

​ (S + sum) / 2===1时无解。S的绝对值已经大于sum时也无解。

​ dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法。不考虑nums[i]的情况下，填满容量为j的背包，有dp[j]种方法。那么考虑nums[i]的话（只要搞到nums[i]），凑成dp[j]就有dp[j - nums[i]] 种方法。

​ dp[j]有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

​ dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。

解法：

var findTargetSumWays = function(nums, target){
    const sum = nums.reduce((a, b)=>a+b);
    if(Math.abs(target)>sum)
        return 0;
    if((target+sum)%2===1)
        return 0;
    const halfSum = (sum+target)/2;
    let dp = new Array(halfSum+1).fill(0);
    dp[0] = 1;
    for(let i=0;i<nums.length;i++)
        for(let j=halfSum;j>=nums[i];j--)
            dp[j] += dp[j-nums[i]];
    return dp[halfSum];
}

一和零

描述：

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例：

示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2： 
输入：strs = ["10", "0", "1"], m = 1, n = 1 
输出：2 
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

思路：

​ strs 数组里的元素就是物品，每个物品都是一个！而m 和 n相当于是一个背包，两个维度的背包。

​ dp[i] [j]：最多有i个0和j个1的strs的最大子集的大小为dp[i] [j]。

​ dp[i] [j] = max(dp[i] [j], dp[i - zeroNum] [j - oneNum] + 1);

解法：

var findMaxForm = function(strs, m, n){
    const dp = new Array(m+1).fill([]).map(()=>new Array(n+1).fill(0));
    let numOfZeros, numOfOnes;
    for(let str of strs){
        numOfOnes = 0;
        numOfZeros = 0;
        for(let c of str)
            if(c==='0')
                numOfZeros++;
            else
                numOfOnes++;
        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];
}

完全背包问题

​ 完全背包和01背包问题不同的地方在于，每种物品有无限件。解题的时候，01背包和完全背包的不同体现在遍历顺序上。01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的，所以要从小到大去遍历。

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { 
        // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

​ 01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序同样无所谓！

var completePack(){
    let weight = [1, 3, 5];
    let value = [15, 20, 30];
    let bagWeight = 4;
    let dp = new Array(bagWeight+1).fill(0);
    for(let i=0;i<weight.length;i++)
        for(let j=weight[i];j<=bagWeight;j++)
            dp[j] = Math.max(dp[j], dp[j-weight[i]]+value[i]);
    return dp[weight.length];
}

​ 先遍历物品，再遍历背包可以用于计算组合数。组合数：{1, 5}，但不会出现{5, 1}的情况。

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}

​ 先遍历背包，再遍历物品可以用于计算排列数。排列数：{1，5}， {5，1}

for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

零钱兑换II

描述：

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例：

示例 1:
输入: amount = 5, coins = [1, 2, 5] 
输出: 4 
解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

示例 2: 
输入: amount = 3, coins = [2] 
输出: 0 
解释: 只用面额2的硬币不能凑成总金额3。

示例 3: 
输入: amount = 10, coins = [10] 
输出: 1

解法：

var change = function(amount, coins){
    let dp = new Array(amount+1).fill(0);
    dp[0] = 1;
    for(let i=0;i<coins.length;i++)
        for(let j=coins[i];j<=amount;j++)
            dp[j]+=dp[j-coins[i]];
    return dp[amount];
}

组合总和IV

描述：

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例：

输入：nums = [1, 2, 3] target = 4
输出：7
解释：(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)请注意，顺序不同的序列被视作不同的组合。

解法：

var combinationSum4 = function(nums, target){
    let dp = new Array(target+1).fill(0);
    dp[0] = 1;
    for(let i=0;i<=target;i++)
        for(let j=0;j<nums.length;j++)
            if(i>=nums[j])
                dp[i] += dp[i-nums[j]];
    return dp[target];
}

爬楼梯升级版

描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 、2 ...m个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路：

​ 1阶，2阶，…. m阶就是物品，楼顶就是背包。每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。问跳到楼顶有几种方法其实就是问装满背包有几种方法。这就是一个完全背包问题了！

解法：

var climb = function(n){
    let dp = new Array(n+1).fill(0);
    const m = 2;
    dp[0] = 1;
    for(let i=0;i<=n;i++)
        for(let j=0;j<=m;j++)
            if(i>=j)
                dp[i]+=dp[i-j];
    return dp[n];
}

零钱兑换

描述：

​ 给定不同面额的硬币 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

示例 4： 
输入：coins = [1], amount = 1 
输出：1

示例 5： 
输入：coins = [1], amount = 2 
输出：2

思路：

​ dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

​ dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

解法：

var coinChange = function(coins, amount){
    if(!amount)
        return 0;
    let dp = new Array(amount+1).fill(Infinity);
    dp[0] = 0;
    for(let i=0;i<coins.length;i++)
        for(let j=coins[i];j<=amount;j++)
            dp[j]=Math.max(dp[j], dp[j-coins[i]]+1);
    return dp[amount]===Infinity?-1:dp[amount];
}

完全平方数

描述：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例：

示例 1： 
输入：n = 12 
输出：3 
解释：12 = 4 + 4 + 4

示例 2： 
输入：n = 13 
输出：2 
解释：13 = 4 + 9

思路：

​ dp[j]：和为j的完全平方数的最少数量为dp[j]

​ dp[j] = min(dp[j - i * i] + 1, dp[j]);

​ 初始化：dp[0]=0(凑数)，非0下标为Infinity

解法：

var numSquares1 = function(n){
    let dp = new Array(n+1).fill(Infinity);
    dp[0] = 0;
    for(let i=1;Math.pow(i,2)<=n;i++)
        for(let j=Math.pow(i,2);j<=n;j++)
            dp[j] = Math.min(dp[j], dp[j-Math.pow(i,2)]+1);
    return dp[n];
}

单词拆分

描述：

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。

示例：

示例 1： 
输入: s = "leetcode", wordDict = ["leet", "code"] 
输出: true 
解释: 返回 true 。因为 "leetcode" 可以被拆分成 "leet code"。

示例 2： 
输入: s = "applepenapple", wordDict = ["apple", "pen"] 
输出: true 
解释: 返回 true 。因为 "applepenapple" 可以被拆分成 "apple pen apple"。注意你可以重复使用字典中的单词。

示例 3： 
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 
输出: false

思路：

​ dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

​ dp[0]初始为true完全就是为了推导公式。下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

解法：

var wordBreak = function(s, wordDict){
    let dp = new Array(s.length+1).fill(0);
    dp[0] = true;
    for(let i=0;i<=s.length;i++)
        for(let j=0;j<wordDict.length;j++)
            if(i>=wordDict[j].length)
                // slice参数(start,end)
                if(s.slice(i-wordDict[j].length, i)===wordDict[j]&&dp[i-wordDict[j].length])
                    dp[i]=true;
    return dp[s.length];
}

打家劫舍

描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例：

示例 1： 
输入：[1,2,3,1] 
输出：4 
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。

示例 2： 
输入：[2,7,9,3,1] 
输出：12 
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路：

​ **dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]**。

​ 如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] 。如果不偷第i房间，那么dp[i] = dp[i - 1]。dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

解法：

var rob = function(nums){
    let len = nums.length;
    if(len===1)
        return nums[0];
    let dp = new Array(len).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for(let i=0;i<len;i++)
        dp[i]=Math.max(dp[i-2]+nums[i], dp[i-1]);
    return dp[len-1];
}

打家劫舍ii

描述：

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例：

示例 1：
输入：nums = [2,3,2] 
输出：3 
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2： 
输入：nums = [1,2,3,1] 
输出：4 
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

示例 3： 
输入：nums = [0] 
输出：0

思路：

​ 对于一个数组，成环的话主要有如下三种情况：不包含首尾元素；考虑包含首元素，不包含尾元素；考虑包含尾元素，不包含首元素。

​ 在第二种方案中，假设不偷最后一间房下，若最大值求得的是没有偷第一间房的情况下的值。那么这种假设中包含了方案一的情况。同理在第三种方案中，也包含了方案一的情况。故实际上只需要考虑方案二和方案三的情况。

解法：

var rob = function(nums){
    let n = nums.length;
    if(n===0)
        return 0;
    if(n===1)
        return nums[0];
    const result1 = robRange(nums, 0, n-2);
    const result2 = robRange(nums, 1, n-1);
    return Math.max(result1, result2);
}
function robRange(nums, start, end){
    if(start===end)
        return nums[end];
    const dp = new Array(nums.length).fill(0);
    dp[start] =nums[start];
    dp[start+1] = Math.max(nums[start], nums[start+1]);
    for(let i=start+2;i<=end;i++)
        dp[i]=Math.max(dp[i-2]+nums[i], dp[i-1]);
    return dp[end];
}

打家劫舍III

描述：

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例：

思路：

​ 本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。

树形dp题，因为是在树上进行状态转移。dp数组是一个长度为2的数组，用于记录一个节点 偷与不偷两个状态所得到的金钱。

解法：

var rob = function(root){
    function postOrder(node){
        if(!node)
            // 空节点时，偷与不偷获得的钱数都是0
            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 donode = node.val + left[0]+right[0];
        return [donot, donode];
    }
    let res = postOrder(root);
    return Math.max(...res);
}

买卖股票的最佳时机（只能买卖一支股票）

描述：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

思路：

​ 重点：股票只能买卖一支！！！

​ dp[i] [j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润。其中：j = 0，表示当前不持股；j = 1，表示当前持股。下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息，因此最后输出 dp[len - 1][0]。

dp[i] [0]：规定了今天不持股，有以下两种情况：

• 昨天不持股，今天什么都不做；
• 昨天持股，今天卖出股票（现金数增加）；

dp[i] [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]);

//第二个式子中不能写成dp[i-1] [0]-prices[i]。因为只允许交易一次，而初始现金是0，所以一直没交易过，昨天不持股今天持股之后手上的现金只剩-prices[i]了。

解法：

var maxProfit = function(prices){
    let len = prices.length;
    if(len<2)
        return 0;
    let dp = [];
    dp[0] = 0;
    dp[1] = -prices[0];
    for(let i=1;i<len;i++){
        dp[0] = Math.max(dp[0], dp[1]+prices[i]);
        dp[1] = Math.max(dp[1], -prices[i]);
    }
    return dp[0];
}

买卖股票的最佳时机II（可买多支股票）

描述：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

思路：

dp[i] [1] = Math.max(dp[i-1] [1], dp[i-1] [0] - prices[i]);
dp[i] [0] = Math.max(dp[i-1] [0], dp[i-1] [1] + prices[i]);

解法：

var maxProfit = function(prices){
    let dp = [0, -prices[0]];
    for(let i=1;i<prices.length;i++){
        dp[0] = Math.max(dp[0], dp[1]+prices[i]);
        dp[1] = Math.max(dp[1], dp[0]-prices[i]);
    }
    return dp[0];
}

买卖股票的最佳时机III(最多完成两次交易)

描述：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

输入：prices = [3,3,5,0,0,3,1,4] 
输出：6 
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。

思路：

一天一共就有五个状态：

1. 没有操作
2. 第一次买入
3. 第一次卖出
4. 第二次买入
5. 第二次卖出

dp[i] [j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i] [j]表示第i天状态j所剩最大现金。

达到dp[i] [1]状态，有两个具体操作：

• 操作一：第i天买入股票了，那么dp[i] [1] = dp[i-1] [0] - prices[i]
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i] [1] = dp[i - 1] [1]

dp[i] [1] = max(dp[i-1] [0] - prices[i], dp[i - 1] [1]);

同理dp[i] [2]也有两个操作：

• 操作一：第i天卖出股票了，那么dp[i] [2] = dp[i - 1] [1] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i] [2] = dp[i - 1] [2]

dp[i] [2] = max(dp[i - 1] [1] + prices[i], dp[i - 1] [2])

同理可推出剩下状态部分：

dp[i] [3] = max(dp[i - 1] [3], dp[i - 1] [2] - prices[i]);

dp[i] [4] = max(dp[i - 1] [4], dp[i - 1] [3] + prices[i]);

初始化：dp[0] [0]=0; dp[0] [1]=-prices[0]; dp[0] [2]=0; dp[0] [3]=-prices[0]; dp[0] [4]=0;

解法：

var maxProfit = function(prices){
    const len = prices.length;
    let dp = [0, -prices[0], 0, -prices[0], 0];
    for(let i=1;i<prices.length;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];
}

买卖股票的最佳时机IV(最多完成k笔交易)

描述：

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

输入：k = 2, prices = [2,4,1] 
输出：2 
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。

思路：

​ 除了0以外，偶数就是卖出，奇数就是买入

解法：

var maxProfit = function(k, prices){
    let n = prices.length;
    let dp = new Array(2*k+1).fill(0);
    // 奇数是买入，偶数是卖出
    for(let i=1;i<=2*k;i+=2)
        dp[i]-=prices[0];
    for(let i=1;i<prices.length;i++)
        for(let j=1;j<2*k+1;j++)
            if(j%2)
                dp[j]=Math.max(dp[j], dp[j-1]-prices[i]);
            else
                dp[j]=Math.max(dp[j], dp[j-1]+prices[i]);
    return dp[2*k];
}

最佳买卖股票时机含冷冻期（可多次交易）

描述：

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例：

输入: [1,2,3,0,2] 
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

思路：

​ dp[i] [j]，第i天状态为j，所剩的最多现金为dp[i] [j]。

​ 具体可以区分出如下四个状态：

• 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
• 卖出股票状态，这里就有两种卖出股票状态
  • 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
  • 状态三：今天卖出了股票
• 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
dp[i][1] = 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];

初始化：dp[0] [0]=-prices[0]; dp[0] [1]=0; dp[0] [2]=0; dp[0] [3]=0;

解法：

var maxProfit = function(prices){
    let n = prices.length;
    // 0是买入 1是卖出，度过了冷冻期 2是卖出 3是冷冻期
    let dp = new Array(4).fill(0);
    dp[0] = -prices[0];
    for(let i=1;i<n;i++){
        dp[0] = Math.max(dp[0], dp[1]-prices[i], dp[3]-prices[i]);
        dp[1] = Math.max(dp[1], dp[3]);
        dp[2] = dp[0]+prices[i];
        dp[3] = dp[2];
    }
    return Math.max(...dp);
}

// 含冷冻期
function maxProfit5(prices){
    /**
     * 0：手上持有股票
     * 1：手上不持股，并且处于冷冻期
     * 2：手上不持股，并且不处于冷冻期
     */
    let dp = [-prices[0],0,0];
    for(let i=0;i<prices.length;i++){
        let temp = [dp[0],dp[1],dp[2]];
        dp[0]=Math.max(temp[0], temp[2]-prices[i]);
        dp[1]=temp[0]+prices[i];
        dp[2]=Math.max(temp[2], temp[1]);
    }
    return Math.max(dp[2], dp[1]);
}

买卖股票的最佳时机含手续费(不限交易次数)

描述：

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例：

输入: 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.

解法：

var maxProfit = function(prices, fee){
    // 0卖出，1买入
    let dp = [0, -prices[0]];
    for(let i=1;i<prices.length;i++){
        dp[0]=Math.max(dp[0], dp[1]+prices[i]-fee);
        dp[1]=Math.max(dp[1], dp[0]-prices[i]);
    }
    return dp[0];
}

最长递增子序列

描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例：

输入：nums = [10,9,2,5,3,7,101,18] 
输出：4 
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

思路：

​ dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度。位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

解法：

var lengthOfLIS = function(nums){
    let dp = new Array(nums.length).fill(1);
    let result = 1;
    for(let i=0;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(dp[i], result);
    }
    return result;
}

最长连续递增序列

描述：

给定一个未经排序的整数数组，找到最长连续递增的子序列，并返回该序列的长度。连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例：

输入：nums = [1,3,5,4,7] 
输出：3 
解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

解法：

// 贪心
var findLengthOfLCITS = function(nums){
    if(nums.length===0)
        return 0;
    let result = 1;
    let count = 1;
    for(let i=0;i<nums.length-1;i++){
        if(nums[i+1]>nums[i])
            count++;
        else
            count=1;
        if(count>result)
            result=count;
    }
    return result;
}

// 动规
var findLengthOfLCITS1 = function(nums){
    let dp = new Array(nums.length).fill(1);
    for(let i=0;nums.length-1;i++)
        if(nums[i+1]>nums[i])
            dp[i+1]=dp[i]+1;
    return Math.max(...dp);
}

最长重复子数组（也就是连续子序列）

描述：

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 
输出：3 
解释： 长度最长的公共子数组是 [3, 2, 1] 。

思路：

​ dp[i] [j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i] [j]。

​ dp[0] [0]=0; dp[i] [0] 和dp[0] [j]初始化为0。

解法：

var findLength = function(nums1, nums2){
    let m = nums1.length;
    let n = nums2.length;
    let dp = new Array(m+1).fill([]).map(()=>new Array(n+1).fill(0));
    let result = 0;
    for(let i=1;i<=m;i++)
        for(let j=1;j<=n;j++){
            if(nums1[i-1]===nums2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            result = Math.max(result, dp[i][j]);
        }
    return result;
}

最长公共子序列

描述：

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。

示例：

输入：text1 = "abcde", text2 = "ace" 
输出：3 
解释：最长公共子序列是 "ace"，它的长度为 3。

思路：

​ dp[i] [j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i] [j]

​ 递推公式的两种情况：

• text1[i - 1] 与 text2[j - 1]相同。如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i] [j] = dp[i - 1] [j - 1] + 1;
• text1[i - 1] 与 text2[j - 1]不相同。看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1]);

解法：

var longestCommonSubsequence = function(text1, text2){
    let n1 = text1.length;
    let n2 = text2.length;
    let dp = new Array(n1+1).fill([]).map(()=>new Array(n2+1).fill(0));
    for(let i=1;i<=n1;i++){
        for(let j=1;j<=n2;j++){
            // 当text1[i-1]=text2[j-1]的时候说明
            // 可以考虑text1[0:i-1]和text2[0:j-1]的最长公共子序列
            if(text1[i-1]===text2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[text1.length][text2.length];
}

最长公共子串[与子序列的区别在于，子序列可以不连续，而子串是连续的]

描述：

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。 

示例：

输入："1AB2345CD","12345EF"
返回值："2345"

思路：

​ dp[i] [j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i] [j]

​ 递推公式的两种情况：

• text1[i - 1] 与 text2[j - 1]相同。如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i] [j] = dp[i - 1] [j - 1] + 1;同时还要记录找到的最长长度以及记录公共子串的尾索引
• text1[i - 1] 与 text2[j - 1]不相同，则置0.

解法：

function LCS( str1 ,  str2 ) {
    let n1=str1.length;
    let n2=str2.length;
    let dp = new Array(n1+1).fill([]).map(()=>new Array(n2+1).fill(0));
    let maxLength = 0, maxLastIndex = 0;
    for(let i=1;i<=n1;i++){
        for(let j=1;j<=n2;j++){
            if(str1[i-1]===str2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
                if(dp[i][j]>maxLength){
                    maxLength=dp[i][j];
                    maxLastIndex=i;
                }
            }else{
                dp[i][j] = 0;
            }
        }
    }
    return str1.substring(maxLastIndex-maxLength, maxLastIndex);
}

不相交的线

描述：

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。以这种方法绘制线条，并返回我们可以绘制的最大连线数。

示例：

思路：

​ 本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

解法：

​ 与最长公共子序列的代码一致

var maxUncrossedLines = function(nums1, nums2) {
    let n1 = nums1.length;
    let n2 = nums2.length;
    let dp = new Array(n1+1).fill([]).map(()=>new Array(n2+1).fill(0));
    for(let i=1;i<=n1;i++)
        for(let j=1;j<=n2;j++){
            if(nums1[i-1]===nums2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
        }
    return dp[n1][n2];
};

最大子序和

描述：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入: [-2,1,-3,4,-1,2,1,-5,4] 
输出: 6 
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路：

dp[i]：包括下标i之前的最大连续子序列和为dp[i]。

dp[i] = max(dp[i - 1] + nums[i], nums[i]);

​ 此处状态的定义不是题目中问题的定义，不能直接把最后一个状态返回回去。题目中的输出是把所有的dp[0]、dp[1]…dp[n-1]都看一遍取最大值，所以代码中需要有一个max变量用于保存最大值。

解法：

// 可用贪心

// 动规
var maxSubArrsy = function(nums){
    let 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-1]+nums[i]将nums[i]加入当前子序
        // nums[i]为从头开始计算子序列和
        dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
        max = Math.max(max, dp[i]);
    }
    return max;
}

判断子序列

描述：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例：

输入：s = "abc", t = "ahbgdc" 
输出：true

思路：

​ **dp[i] [j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i] [j]**。这样定义可以在二维矩阵中留出初始化区间。

有两种情况：

• s[i-1]=t[j-1]：t中找到了一个字符在s中也出现了。那么dp[i] [j] = dp[i - 1] [j - 1] + 1。
• s[i-1]!=t[j-1]：相当于t要删除元素，继续匹配。t如果把当前元素t[j - 1]删除，那么dp[i] [j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i] [j] = dp[i] [j - 1];

这个题与最长公共子序列很相似，只是在计算的过程中少了s[i-1] [j]的情况。

解法：

var isSubsequence = function(s, t){
    let m = s.length;
    let n = t.length;
    let dp = new Array(m+1).fill([]).map(()=>new Array(n+1).fill(0));
    for(let i=1;i<=m;i++)
        for(let j=1;j<=n;j++){
            if(s[i]===t[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=dp[i][j-1];
        }
    return dp[m][n]===m?true:false;
}

不同的子序列

【困难题】

描述：

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）。题目数据保证答案符合 32 位带符号整数范围。

示例：

思路：

​ dp[i] [j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i] [j]。

​ 两种情况需要考虑：

• s[i-1]与t[j-1]相等。dp[i] [j]可以由两部分组成。一部分是用s[i - 1]来匹配，那么个数为dp[i - 1] [j - 1]。一部分是不用s[i - 1]来匹配，个数为dp[i - 1] [j]。故dp[i] [j] = dp[i - 1] [j - 1] + dp[i - 1] [j];
• s[i - 1] 与 t[j - 1]不相等。dp[i] [j] = dp[i - 1] [j];

解法：

var numDistinct = function(s, t){
    let dp = new Array(s.length+1).fill([]).map(()=>new Array(t.length+1).fill(0));
    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];
    return dp[s.length][t.length];
}

斐波那契数列

描述：

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例：

输入：n = 2
输出：1

解法：[动态规划]

var fib = function(n) {
    let dp = new Array(n+1).fill(0);
    dp[1]=1;
    for(let i=2;i<=n;i++)
        dp[i]=(dp[i-1]+dp[i-2])%1000000007;
    return dp[n];
};

最长回文子串

描述：

给你一个字符串 s，找到 s 中最长的回文子串

示例：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

思路：

​ dp[i] [j]表示字符串s的第i到j个字母组成的串是否是回文串。

​ 初始化条件：dp[i] [i]是回文串。

解法：

function getLongestPalindrome( A ) {
    // write code here
    let n = A.length;
    if(n<2)
        return A.length;
    let dp = new Array(n).fill([]).map(()=>new Array(n));
    let max_len = 1;
    // 初始化
    for(let i=0;i<n;i++)
        dp[i][i]=true;
    // 枚举子串的长度
    for(let L=2;L<n+1;L++){
        for(let i=0;i<n;i++){
            j = L+i-1;
            // 右边界越界
            if(j>=n)
                break;
            // 不是回文串
            if(A[i]!==A[j])
                dp[i][j]=false;
            else{
                if(j-i<3)
                    dp[i][j]=true;
                else
                    dp[i][j]=dp[i+1][j-1];
            }
            if(dp[i][j] && (j-i+1>max_len)){
                max_len = j-i+1;
            }
        }
    }
    return max_len;
}

相似的题目：

• 整数拆分、不同的二叉搜索树
• 拆分成两部分：分割等和子集、最后一块石头的重量II、目标和
• 零钱兑换II(组合数)、组合总和IV(排列数)、爬楼梯升级版
• 零钱兑换、完全平方数、单词拆分
• [最长公共子序列、不相交的线]解法完全一致、判断子序列、不同的子序列
• 最长递增子序列、最长连续递增序列、最长重复子串：这些都需要有一个result来存放最大的值

总结：

• 纯背包问题是能否凑成一定的数量，动态规划的形式为：dp[j]=Math.max(dp[j], dp[j-weight[i]]+value[i])
• 组合数形式的背包问题是凑成这个数量的方案有几种，动态规划的形式为：dp[j]+=dp[j-weight[i]]
• 计算排列数时dp[0]初始化为1
• 计算最小数时，dp数组初始化值为Infinity，dp[0]=0
• 最长子序列初始值为1

注意点：

• 初始化的时候要注意到底是0还是1还是Infinity还是-Infinity

错题：

• 最后一块石头的重量dp[j]表示的是容量为j的背包所能装下的最大物品重量
• 目标和与组合总和搞混
• 零钱兑换初始化存在问题，整个数组初始化为Infinity，但是dp[0]应该初始化为0
• 打家劫舍IIdp数组初始化长度以及遍历时下标易出错；打家劫舍III不会做(树形动规)
• 最佳买卖股票时机含冷冻期dp递推关系错误