十七 算法-动态规划

动态规划

动规基础、背包问题、打家劫舍、股票问题、子序列问题

确定dp数组（dp table）以及 dp[i] 的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
打印dp数组

1. 斐波那契数

509简单

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1 2	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, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    console.log(dp)
    return dp[n]
};

2. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

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

dp[i]：爬到第i层楼梯，有dp[i]种方法

确定递推公式

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

dp数组如何初始化 dp[1] = 1，dp[2] = 2
确定遍历顺序遍历顺序一定是从前向后遍历的
举例推导dp数组

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

3. 使用最小花费爬楼梯

746

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

解题思路：

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
dp数组如何初始化 dp[0] = 0，dp[1] = 0;
确立遍历顺序
打印dp数组

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    let dp=[0,0]
    let len=cost.length
    for(let i=2;i<=len;i++){
        dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
    }
    console.log(dp)
    return dp[len]
};

4. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

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

2、dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。

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

4、dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

5、举例推导dp数组

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const arr=Array.from(new Array(m).fill(1), () => new Array(n).fill(1))
     for (let i = 1; i < m; i++) {
            for (let j = 1; j < n; j++) {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
        }
    return arr[m-1][n-1]
};

5. 不同路径II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

初始化：

vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length
    const n = obstacleGrid[0].length
    const dp = Array(m).fill().map(item => Array(n).fill(0))
    
    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) {
            dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]
        }
    }
        
    return dp[m - 1][n - 1]
};

6. 整数拆分

343

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

1
2
3

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

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

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

确定递推公式

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

比如整数i:，拆分成j和（i-j）,或者i-j再拆分，取他们的积最大的max({dp[i], (i - j) j, dp[i - j] j}); 同时j的值也是变化的

dp的初始化

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

确定遍历顺序

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

举例推导dp数组

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    let dp=new Array(n+1).fill(0)
    dp[2]=1
    for(let i=2;i<=n;i++){
        for(let j=1;j<i;j++){ // 这里可以写成j<i/2,因为4*6和6*4一样
            dp[i]=Math.max(j*(i-j),j*dp[i-j],dp[i])
        }
    }
    console.log(dp)
    return dp[n]
};

7. 两个字符串中的最长公共子串

8. 最长回文子串

9. 不同的二叉搜索树

96 中等

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]
确定递推公式

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

dp数组如何初始化

dp[0]=1 dp[1]=1

const numTrees =(n) => {
    let dp = new Array(n+1).fill(0);
    dp[0] = 1;
    dp[1] = 1;

    for(let i = 2; i <= n; i++) {
        for(let j = 1; j <= i; j++) {
            dp[i] += dp[j-1] * dp[i-j];
        }
    }

    return dp[n];
};

不同的二叉搜索树

https://leetcode.cn/problems/unique-binary-search-trees/solutions/550154/96-bu-tong-de-er-cha-sou-suo-shu-dong-ta-vn6x/

背包问题

10. 0-1背包问题

这里有4个物品，重量分别为[1, 3, 4, 5]，价值分别为[15, 20, 30, 55]，有个背包能装重量为6的东西，怎么才能装价值最大的。

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

对于背包问题，有一种写法，是使用二维数组，即dp [i] [j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

确定递推公式

 //**不放物品i**：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
 //**放物品i**：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

//	所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp数组如何初始化

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
------------------------------
// 其他下标应该初始化多少呢 零比较好，所以只用初始化第一行能装下物品的部分
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

确定遍历顺序

有两个遍历的维度：物品与背包重量

5….

function testWeightBagProblem (weight, value, size) {
    // 定义 dp 数组
    const len = weight.length,
          dp = Array(len).fill().map(() => Array(size + 1).fill(0));

    // 初始化
    for(let j = weight[0]; j <= size; j++) {
        dp[0][j] = value[0];
    }

    // weight 数组的长度len 就是物品个数
    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]);
        }
    }

    console.table(dp)

    return dp[len - 1][size];
}

function test () {
    console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}

test();

11. 01背包滚动数组

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

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


3. 都为0

   

4. ```js
   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，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下

    function testWeightBagProblem(wight, value, size) {
      const len = wight.length, 
      dp = Array(size + 1).fill(0);
      for(let i = 0; i < len; i++) {
        for(let j = size; j >= wight[i]; j--) {
          dp[j] = Math.max(dp[j], value[i] + dp[j - wight[i]]);
        }
        console.log(dp)
      }
      return dp[size];

    }


function test () {
  console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}

test();

12. 分割等和子集

416

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

1
2
3

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

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

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

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

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

本题中每一个元素的数值既是重量，也是价值。

确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

所以本题递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

dp数组如何初始化

都初始化为0

4. 确定遍历顺序

倒叙遍历

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}

举例推导dp数组

var canPartition = function(nums) {
    const sum = (nums.reduce((p, v) => p + v));// 累加
    if (sum & 1) return false;  // 判断奇数偶数
    const dp = Array(sum / 2 + 1).fill(0);
    for(let i = 0; i < nums.length; i++) {
        for(let j = sum / 2; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            if (dp[j] === sum / 2) {
                return true;
            }
        }
    }
    return dp[sum / 2] === sum / 2;
};

13. 最后一块石头重量II

1049

和上一道题特别像

分成大小相近的两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。最后相减

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function(stones) {
    let sum=stones.reduce((p,c)=>p+c)
    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] )
        }
    }
    return sum-dp[target]-dp[target]

};

14. 目标和

494

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

left代表+之数的和，right代表-之数的和

left+right=sum, left-right=target ——————> left=(sum+target)/2

1、dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

2、例如：dp[j]，j 为5，

已经有一个1（nums[i]）的话，有 dp[4]种方法凑成容量为5的背包。
已经有一个2（nums[i]）的话，有 dp[3]种方法凑成容量为5的背包。
已经有一个3（nums[i]）的话，有 dp[2]中方法凑成容量为5的背包
已经有一个4（nums[i]）的话，有 dp[1]中方法凑成容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法凑成容量为5的背包

那么凑整dp[5]有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。

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

3、dp数组如何初始化 dp[0]=1

4、先遍历物品，再遍历背包

5、举例推导dp数组

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    const sum = nums.reduce((a, b) => a+b);
    
    if(Math.abs(target) > sum) {
        return 0;
    }

    if((target + sum) % 2) {
        return 0;
    }

    const halfSum = (target + sum) / 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];
};

完全背包

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件

同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理

和01背包滚动数组的区别是，遍历顺序从前往后遍历，两个for循环可以互换

// 首先在回顾一下01背包的核心代码
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]); // 倒序遍历 每个物品只遍历一次 递推过来的时候 之前的值才初始化
    }
}

// 完全背包
// 先遍历物品，再遍历背包
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]); // 顺序遍历

    }
}

15. 零钱兑换II

518

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

1、 dp[j]：凑成总金额j的货币组合数为dp[j]

2、dp[j] += dp[j - coins[i]] 为什么是这样在14题 目标和中给出了

3、dp[0]=1 ,其他为0

4、外层for循环遍历物品，内层for遍历背包为组合数，就是不讲究顺序。如本体

外层for循环遍历背包，内层for遍历物品为排列数，就是讲究顺序。如下一题

5、dp打印

const change = (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++) {
            dp[j] += dp[j - coins[i]];
        }
    }

    return dp[amount];
}

16. 组合总和IV

377

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

dp[i]: 凑成目标正整数为i的排列个数为dp[i]
dp[i] += dp[i - nums[j]];
dp[0]=1 其他为0
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
举例来推导dp数组

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    let dp=new Array(target+1).fill(0)
    dp[0]=1
    for(let j=0;j<=target;j++){  // 遍历背包
        for(let i=0;i<nums.length;i++){  // 遍历物品
            if(j>=nums[i]){    // 判断背包是否能装下物品               
                dp[j]+=dp[j-nums[i]] 
            }
        }
    }
    return dp[target]
};

17. 零钱兑换

322

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

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

2、递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]，所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

3、dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;下标非0的元素都是应该是最大值。

4、确定遍历顺序两种都行

5、打印dp

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    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.min(dp[j-coins[i]]+1,dp[j])
        }
    }
    return dp[amount]==Infinity?-1:dp[amount]
};

18. 完全平方数

279

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

这道题的解题思路和上面的完全一样。

1、dp[j]：凑足和为j所需完全平方数的最少个数为dp[j]

2、dp[j]=Math.min(dp[j-i*i]+1,dp[j])

3、dp[0]=0 其他为Infinity

4、都行

5、打印dp

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    let dp=new Array(n+1).fill(Infinity)
    dp[0]=0
    for(let i=1;i*i<=n;i++){
        for(let j=i*i;j<=n;j++)
        dp[j]=Math.min(dp[j-i*i]+1,dp[j])
    }
    return dp[n]
};

19. 打家劫舍

198

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

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

2、决定dp[i]的因素就是第i房间偷还是不偷。dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3、dp数组如何初始化，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值，其他什么都行

4、确定遍历顺序，dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

5、举例推导dp数组以示例二，输入[2,7,9,3,1]为例

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

20. 打家劫舍II

213

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

思路：这道题目和198.打家劫舍 (opens new window)是差不多的，唯一区别就是成环了。

1、考虑不包含首尾元素

2、考虑包含首元素，不包含尾元素

3、考虑包含尾元素，不包含首元素

而情况二和情况三都包含了情况一了，所以只考虑情况二和情况三就可以了。

然后把数据的数组进行拆分，然后传到打家劫舍I的函数中去，最后比较结果

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length==1){
        return nums[0]
    }
    // 打家劫舍I的函数
    function steal(arr){
        let dp=new Array(arr.length).fill(0)
        dp[0]=arr[0]
        dp[1]=Math.max(arr[0],arr[1])
        for(let i=2;i<arr.length;i++){
            dp[i]=Math.max(dp[i-2]+arr[i],dp[i-1])
        }
        return dp[arr.length-1]
    }
    // 把数组拆分两段，传入进去，最后比较结果
    let res1=steal(nums.slice(0,nums.length-1))
    let res2=steal(nums.slice(1))
    return Math.max(res1,res2)
};

21. 打家劫舍III

337

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

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

思路：这是一个树状的结构

采用后序遍历，如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）

1、确定递归函数的参数和返回值

这里我们要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。dp[0]代表不偷当前结点，dp[1]代表偷

2、确定终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

3、确定遍历顺序

首先明确的是使用后序遍历。因为要通过递归函数的返回值来做下一步计算。

通过递归左节点，得到左节点偷与不偷的金钱。

通过递归右节点，得到右节点偷与不偷的金钱。

1 2	let leftdp=dfs(cur.left) let rightdp=dfs(cur.right)

4、确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

5、举例推导dp数组

以示例1为例，dp数组状态如下：（注意用后序遍历的方式推导）

/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    const dfs=(cur)=>{
        if(cur==null) return [0,0]
        let leftdp=dfs(cur.left)
        let rightdp=dfs(cur.right)

        let valSteal=cur.val+leftdp[0]+rightdp[0]
        let valNoSteal=Math.max(leftdp[0],leftdp[1])+Math.max(rightdp[0],rightdp[1])
        return [valNoSteal,valSteal]
    }
    let dp=dfs(root)
    return Math.max(dp[0],dp[1])
};

22. 买卖股票的最佳时机

121

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

可以用贪心算法

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let minPrices=prices[0]
    let profitMax=0
    for(let i=0;i<prices.length;i++){
        if(prices[i]<minPrices){
            minPrices=prices[i]
        }
        profitMax=Math.max(prices[i]-minPrices,profitMax)
    }
    return profitMax
};

可以用动态规划

1、 dp[i] [0] 表示第i天不持有股票所得最多现金，dp[i] [1] 表示第i天持有股票所得最多现金

2、

//第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][0]
//第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][1]
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])

//第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][1]
//第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
dp[i][1]=Math.max(dp[i-1][1],-prices[i])

3、dp数组如何初始化

1 2	dp[0][0]=0 // 未持有 dp[0][1]=-prices[0] // 持有

4、从前往后

5、dp

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp=new Array(prices.length).fill(0).map(()=>new Array(2).fill(0))
    dp[0][0]=0 // 未持有
    dp[0][1]=-prices[0] // 持有
    for(let i=1;i<prices.length;i++){
        dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])
        dp[i][1]=Math.max(dp[i-1][1],-prices[i])
    }
    return dp[prices.length-1][0]
};

23. 买卖股票的最佳时机II

122

给定一个数组，它的第 i 个元素是一支给定股票第 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]) 区别在这里
dp[i][1]=Math.max(dp[i-1][1],d[i-1][0]-prices[i])  


/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp=new Array(prices.length).fill(0).map(()=>new Array(2).fill(0))
    dp[0][0]=0 // 未持有
    dp[0][1]=-prices[0] // 持有
    for(let i=1;i<prices.length;i++){
        dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])
        dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i])
    }
    return dp[prices.length-1][0]
};

这道题用贪心算法很快的

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    
    let total=0
    for(let i=0;i<prices.length-1;i++){
        total+=Math.max(prices[i+1]-prices[i],0)
    }
    return total
};

24. 买卖股票最佳时机III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

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

一天一共就有五个状态，

没有操作（其实我们也可以不设置这个状态）
第一次持有股票 dp[i] [1]
第一次不持有股票 dp[i] [2]
第二次持有股票 dp[i] [3]
第二次不持有股票 dp[i] [4]

2、确定递推公式

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

3、dp数组如何初始化

dp[0][0]=0  		// 第0天没有操作
   dp[0][1]=-prices[0] // 第0天做第一次买入的操作
   dp[0][2]=0			// 第0天做第一次卖出的操作
   dp[0][3]=-prices[0] // 第0天第二次买入操作
   dp[0][4]=0			// 第0天做第二次卖出的操作

4、确定遍历顺序

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

5、举例推导dp数组

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp=new Array(prices.length).fill(0).map(()=>new Array(4).fill(0))
    
    dp[0][0]=0
    dp[0][1]=-prices[0]
    dp[0][2]=0
    dp[0][3]=-prices[0]
    dp[0][4]=0
    for(let i=1;i<prices.length;i++){
        dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i])
        dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i])
        dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i])
        dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i])
    }
    return dp[prices.length-1][4]
};

// 优化
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const len = prices.length;
    const dp = new Array(5).fill(0);
    dp[1] = -prices[0];
    dp[3] = -prices[0];
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], dp[0] - prices[i]);
        dp[2] = Math.max(dp[2], dp[1] + prices[i]);
        dp[3] = Math.max(dp[3], dp[2] - prices[i]);
        dp[4] = Math.max(dp[4], dp[3] + prices[i]);
    }
    return dp[4]
};

25. 买卖股票的最佳时机IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

这道题思路和上一道一样，只是变成了k次交易

1、同上

2、确定递推公式

for(let j=0;j<2*k;j+=2){
   dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i])
   dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i])
}

3、dp数组如何初始化

1
2
3

for(let i=1;i<2*k;i+=2){
        dp[0][i]=-prices[0]
}

4、同上

5、同上

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
    let dp=new Array(prices.length).fill(0).map(()=>new Array(2*k+1).fill(0))
    for(let i=1;i<2*k;i+=2){
        dp[0][i]=-prices[0]
    }
    for(let i=1;i<prices.length;i++){
        for(let j=0;j<2*k;j+=2){
            dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i])
            dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i])
        }
    }
    return dp[prices.length-1][2*k]
};

// 优化
var maxProfit = function(k, prices) {
    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=0;j<2*k;j+=2){
            dp[j+1]=Math.max(dp[j+1],dp[j]-prices[i])
            dp[j+2]=Math.max(dp[j+2],dp[j+1]+prices[i])
        }
    }
    return dp[2*k]
};

26. 买卖股票的最佳时机含冷冻期

309

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

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

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

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

其实本题很多同学搞的比较懵，是因为出现冷冻期之后，状态其实是比较复杂度，例如今天买入股票、今天卖出股票、今天是冷冻期，都是不能操作股票的。

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

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

2、递推公式

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];												   // 冷冻期

3、初始化

dp[0] [0] = -prices[0] 其他为0

4、遍历顺序就是正常的顺序

5、dp数组

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(prices.length < 2) {
        return 0
    } else if(prices.length < 3) {
        return Math.max(0, prices[1] - prices[0]);
    }

    let dp = Array.from(Array(prices.length), () => Array(4).fill(0));
    dp[0][0] = 0 - prices[0];

    for(i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i-1][1], dp[i-1][3]) - prices[i]);
        dp[i][1] = Math.max(dp[i -1][1], dp[i - 1][3]);
        dp[i][2] = dp[i-1][0] + prices[i];
        dp[i][3] = dp[i-1][2];
    }

    return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2], dp[prices.length - 1][3]);

};

27. 买卖股票的最佳时机含手续费

714

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

这道题很简单和23II差不多

递推公式：

dp[i] [0] 表示第i天持有股票所省最多现金。 dp[i] [1] 表示第i天不持有股票所得最多现金

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


//简化：
dp[0]=Math.max(dp[0],dp[1]-prices[i]) 
dp[1]=Math.max(dp[1],dp[0]+prices[i]-fee)

const maxProfit = (prices,fee) => {
    let dp = Array.from(Array(prices.length), () => Array(2).fill(0));
    dp[0][0] = 0 - prices[0];
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
    }
    return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
}

// 简化
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    let dp=[-prices[0],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]-fee)
    }
    return dp[1]
};

28. 最长连续递增序列

674

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

1、dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。

2、确定递推公式。if(nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;

3、以下标i为结尾的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。所以dp[i]应该初始1;

4、遍历顺序，就是从前往后遍历。

for (int i = 1; i < nums.size(); i++) {
    if (nums[i] > nums[i - 1]) { // 连续记录
        dp[i] = dp[i - 1] + 1;
    }
}

5、打印dp

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    let dp=new Array(nums.length).fill(1)
    let res=1
    for(let i=1;i<nums.length;i++){
        if(nums[i]>nums[i-1]){
            dp[i]=dp[i-1]+1
        } 
        res=Math.max(res,dp[i]) // 找到最大dp值
    }
    return res
};

29. 最长上升子序列

300

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1
2
3

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

1、dp[i]表示以nums[i]结尾的最长递增子序列的长度

2、位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

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

3、dp[i]的初始化，每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.

4、确定遍历顺序，dp[i] 是有0到i-1各个位置的最长递增子序列推导而来，那么遍历i一定是从前向后遍历。

for (int i = 1; i < nums.size(); i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
    }
    if (dp[i] > result) result = dp[i]; // 取长的子序列
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let dp=new Array(nums.length).fill(1)
    let res=1
    for(let i=1;i<nums.length;i++){
        for(let j=0;j<i;j++){
            if(nums[i]>nums[j])
            dp[i]=Math.max(dp[j]+1,dp[i])
        }
        res=Math.max(dp[i],res)  // 需要遍历dp[i]取得最大值
    }
    return res

};

30. 最长重复子数组

718

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

1
2
3

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

解题思路：二维数组，横轴和纵轴上相等的为一，不等的为0，找出最长连续的斜线

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

2、即当A[i - 1] 和B[j - 1]相等的时候，dp[i] [j] = dp[i - 1] [j - 1] + 1;

3、根据dp[i][j]的定义，dp[i] [0] 和dp[0] [j]其实都是没有意义的！但dp[i] [0] 和dp[0] [j]要初始值，因为为了方便递归公式dp[i] [j] = dp[i - 1] [j - 1] + 1;所以dp[i] [0] 和dp[0] [j]初始化为0。

4、

for(let i=1;i<=nums1.length;i++){
    for(let j=1;j<=nums2.length;j++){
        if(nums1[i-1]==nums2[j-1]){
            dp[i][j]=dp[i-1][j-1]+1
        }
        res=Math.max(dp[i][j],res)
    }
}

5、打印dp

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function(nums1, nums2) {
    const dp=new Array(nums1.length+1).fill().map(()=>new Array(nums2.length+1).fill(0))
    let res=0
    for(let i=1;i<=nums1.length;i++){
        for(let j=1;j<=nums2.length;j++){
            if(nums1[i-1]==nums2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1
            }
            res=Math.max(dp[i][j],res)
        }
    }
    return res
};

31. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

1
2
3

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

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

2、 text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

if (text1[i - 1] == text2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

3、 dp数组如何初始化

dp[i] [0] =0，dp[0] [j]也是0。

4、有三个方向可以推出dp[i] [j]

5、以输入：text1 = “abcde”, text2 = “ace” 为例，dp状态如图：

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    const dp=new Array(text1.length+1).fill().map(()=>new Array(text2.length+1).fill(0))
    for(let i=1;i<=text1.length;i++){
        for(let j=1;j<=text2.length;j++){
            if(text1[i-1]==text2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1
            }else{
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    return dp[text1.length][text2.length]
};

33. 不相交的线

1035

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

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

思路算法都和上一题一样

34. 最大子序和

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

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

1、dp[i]：以nums[i]为结尾的最大连续子序列和为dp[i]。

2、dp[i]只有两个方向可以推出来：

dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
nums[i]，即：从头开始计算当前连续子序列和

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

3、初始化，从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。dp[0] = nums[0]

4、递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

5、举例推导dp数组

const maxSubArray = nums => {
    // 数组长度，dp初始化
    const len = nums.length;
    let dp = new Array(len).fill(0);
    dp[0] = nums[0];
    // 最大值初始化为dp[0]
    let max = dp[0];
    for (let i = 1; i < len; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        // 更新最大值
        max = Math.max(max, dp[i]);
    }
    return max;
};

35. 不同的子序列

115

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

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

2、这一类问题，基本是要分析两种情况

s[i - 1] 与 t[j - 1]相等 dp[i] [j]可以有两部分组成。

一部分是用s[i - 1]来匹配，那么个数为dp[i - 1] [j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1] [j-1]。

一部分是不用s[i - 1]来匹配，个数为dp[i - 1] [j]。例如s：bagg 和 t：bag ，s[3] 和 t[2]是相同的

dp[i] [j] = dp[i - 1] [j - 1] + dp[i - 1] [j];
s[i - 1] 与 t[j - 1] 不相等 dp[i] [j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1] [j]

3、从递推公式dp[i][j] = dp[i - 1] [j - 1] + dp[i - 1] [j]; 和 dp[i][j] = dp[i - 1] [j]; 中可以看出dp[i][j] 是从上方和左上方推导而来，如图：，那么 dp[i] [0] 和dp[0] [j]是一定要初始化的。

dp[i] [0]=1 dp[0] [0]=1 dp[0] [j]=0

dp[i] [0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。

dp[0] [j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。

4、遍历顺序

可以看出dp[i][j]都是根据左上方和正上方推出来的。

5、打印dp

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
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]
};

36. 两个字符串的删除操作

583

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

1
2
3

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

另一种思路：本题和动态规划：1143.最长公共子序列基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

1、dp[i] [j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

2、

当word1[i - 1] 与 word2[j - 1]相同的时候 dp[i] [j] = dp[i - 1] [j - 1]
当word1[i - 1] 与 word2[j - 1]不相同的时候

情况一：删word1[i - 1]，最少操作次数为dp[i - 1] [j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i] [j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1] [j - 1] + 2

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

3、初始化

for (let i = 1; i <= word1.length; i++) {
  dp[i][0] = i;
}
for (let j = 1; j <= word2.length; j++) {
  dp[0][j] = j;
}

4、顺序

5、dp

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let dp = Array.from(new Array(word1.length + 1), () =>Array(word2.length + 1).fill(0));
    for (let i = 1; i <= word1.length; i++) {
        dp[i][0] = i;
    }
    for (let j = 1; j <= word2.length; j++) {
        dp[0][j] = j;
    }
    for (let i = 1; i <= word1.length; i++) {
        for (let j = 1; j <= word2.length; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                dp[i - 1][j] + 1,
                dp[i][j - 1] + 1,
                dp[i - 1][j - 1] + 2
                );
            }
        }
    }
    return dp[word1.length][word2.length];
};

37. 编辑距离

72 难

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

1、dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i] [j]。

2、确定递推公式

if (word1[i - 1] == word2[j - 1])
    dp[i][j] = dp[i - 1][j - 1] //不操作
if (word1[i - 1] != word2[j - 1])
    // 下面取min
    dp[i][j] = dp[i - 1][j] + 1 	// word1删除一个元素
    dp[i][j] = dp[i][j - 1] + 1;	// 增， word2删除一个元素，其实就是word1增加一个元素
    dp[i][j] = dp[i - 1][j - 1] + 1 // 换,比如ab和ac在dp[i-1][j-1]的基础上，进行替换

3、初始化

那么dp[i] [0]就应该是i，对word1里的元素全部做删除操作，即：dp[i] [0] = i; 同理dp[0] [j] = j;

4、

5、打印dp

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let dp=new Array(word1.length+1).fill().map(()=>new Array(word2.length+1).fill(0))
    // 初始化
    for(let i=0;i<=word1.length;i++){
        dp[i][0]=i
    }
    for(let j=0;j<=word2.length;j++){
        dp[0][j]=j
    }
    // 遍历顺序
    for(let i=1;i<=word1.length;i++){
        for(let j=1;j<=word2.length;j++){
            // 递推公式
            if(word1[i-1]==word2[j-1]){
                dp[i][j]=dp[i-1][j-1]
            }else{
                dp[i][j]=Math.min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
            }
        }
    }
    return dp[word1.length][word2.length]
};

38. 回文子串

647 中

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

1
2
3

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

1、布尔类型的dp[i] [j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i] [j]为true，否则为false。

2、就是s[i]与s[j]相等，s[i]与s[j]不相等这两种

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是回文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1] [j - 1]是否为true

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        result++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        result++;
        dp[i][j] = true;
    }
}

result就是统计回文子串的数量。

3、dp[i] [j]可以初始化为true么？当然不行，怎能刚开始就全都匹配上了。

所以dp[i] [j]初始化为false。

4、情况三是根据dp[i + 1] [j - 1]是否为true，在对dp[i] [j]进行赋值true的。dp[i + 1] [j - 1] 在 dp[i][j]的左下角，如图：

所以一定要从下到上，从左到右遍历，这样保证dp[i + 1] [j - 1]都是经过计算的

5、

注意因为dp[i] [j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let dp=new Array(s.length).fill().map(()=>new Array(s.length).fill(false))
    let numOfPalindromicStr=0
    for(let i=s.length-1;i>=0;i--){
        for(let j=i;j<s.length;j++){
            if(s[i]===s[j]){
                if(j-i<=1){
                    dp[i][j]=true
                    numOfPalindromicStr+=1
                }else if(dp[i+1][j-1]) {
                    dp[i][j]=true
                    numOfPalindromicStr+=1
                }
            }
        }
    }
    return numOfPalindromicStr
};

39. 最长回文子串

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

1
2
3

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

1、布尔类型的dp[i] [j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i] [j]为true，否则为false。

2、就是s[i]与s[j]相等，s[i]与s[j]不相等这两种

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是回文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1] [j - 1]是否为true

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        dp[i][j] = true;
    }
}
if(dp[i][j]&&j-i+1>maxLength){ // 判断是否最大长度
                maxLength=j-i+1
                left=i
                right=j
            }

后面和上一题完全一样

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let dp=new Array(s.length).fill().map(()=>new Array(s.length).fill(false))
    let maxLength=0
    let left=0
    let right=0
    for(let i=s.length-1;i>=0;i--){
        for(let j=i;j<s.length;j++){
            if(s[i]==s[j]){
                if(j-i<=1){
                    dp[i][j]=true
                }else if(dp[i+1][j-1]){
                    dp[i][j]=true
                }
            }
            if(dp[i][j]&&j-i+1>maxLength){
                maxLength=j-i+1
                left=i
                right=j
            }
        }
    }
    return s.slice(left,right+1)
};

40. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

1
2
3

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

回文子串是要连续的，回文子序列可不是连续的

1、dp[i] [j]：字符串s在[i, j]范围内最长的回文子序列的长度

2、如果s[i]与s[j]相同，那么dp[i] [j] = dp[i + 1] [j - 1] + 2;

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。加入s[j]的回文子序列长度为dp[i + 1] [j]。加入s[i]的回文子序列长度为dp[i] [j - 1]。

那么dp[i] [j]一定是取最大的，即：dp[i] [j] = max(dp[i + 1] [j], dp[i] [j - 1]);

3、首先要考虑当i 和j 相同的情况，从递推公式：dp[i] [j] = dp[i + 1] [j - 1] + 2; 可以看出递推公式是计算不到 i 和j相同时候的情况。

所以需要手动初始化一下，当i与j相同，那么dp[i] [j]一定是等于1的，其他情况dp[i][j]初始为0就行。

4、遍历顺序

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
    let dp=new Array(s.length).fill().map(()=>new Array(s.length).fill(0))
    for(let i=0;i<s.length;i++){
        dp[i][i]=1
    }
    for(let i=s.length-1;i>=0;i--){
        for(let j=i+1;j<s.length;j++){
            if(s[i]==s[j]){
                dp[i][j]=dp[i+1][j-1]+2
            }else{
                dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j])
            }
        }
    }
    return dp[0][s.length-1]
};