动态规划.png

1. 动态规划概述

（1）基本概念

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，而我们希望找到具有最优值的解。动态规划算法与分治法类似，基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

动态规划问题经分解得到的子问题往往不是互相独立的。需要保存已解决的子问题的答案，而在需要时再找出已保存的答案，这样就可以避免大量的重复计算。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

动态规划有两个重要的概念：

  • 状态：解决某一问题的中间结果，它是子问题的一个抽象定义。
  • 状态转移方程：状态与状态之间的递推关系。

动态规划解题步骤：

  1. 状态定义：找出子问题抽象定义。
  2. 确定状态转移方程：找出状态与状态之间的递推关系。
  3. 初始状态和边界情况：最简单的子问题的结果，也是程序的出口条件 。
  4. 返回值：对于简单问题，返回值可能就是最终状态；对于复杂问题可能还需对最终状态做一些额外处理。

下面就通过爬楼梯问题来看看动态规划的具体应用。

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

示例 1：

  1. 输入： 2
  2. 输出： 2
  3. 解释： 有两种方法可以爬到楼顶。
  4. 1. 1 阶 + 1 阶
  5. 2. 2 阶

示例 2：

  1. 输入： 3
  2. 输出： 3
  3. 解释： 有三种方法可以爬到楼顶。
  4. 1. 1 阶 + 1 阶 + 1 阶
  5. 2. 1 阶 + 2 阶
  6. 3. 2 阶 + 1 阶

这道题有两个关键特征：

  • 要求给出达成某个目的的解法个数；
  • 不要求给出每一种解法对应的具体路径。

这样的问题往往可以用动态规划进行求解。对于这个问题，每次爬楼梯只有两种情况：

  • 最后一步爬 1 级台阶，前面有 n - 1 级台阶，这种情况下共有f(n - 1)种方法；
  • 最后一步爬 2 级台阶，前面有 n - 2 级台阶，这种情况下共有f(n - 2)种方法；

f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)，这就是本题用到的递推关系。下面就根据动态规划的四个步骤来看那一下：

  1. 状态定义：初始化一个f数组，f[i]表示爬到i级台阶的方法数量；
  2. 状态转移方程：f(n)=f(n-1)+f(n-2)；
  3. 初始状态：一级台阶时，共1种爬法；两级台阶时，可以一级一级爬，也可以一次爬两级，共有2种爬法。即f[1] = 1，f[2] = 2；
  4. 返回值：f[n] ，即 n 级台阶共有多少种爬法。

动态规划实现代码如下：

  1. /**
  2. * @param {number} n
  3. * @return {number}
  4. */
  5. const climbStairs = function(n) {
  6.     // 初始化状态数组
  7.     const f = [];
  8.     // 初始化已知值
  9.     f[1] = 1;
  10.     f[2] = 2;
  11.     // 动态更新每一层楼梯对应的结果
  12.     for(let i = 3;i <= n;i++){
  13.         f[i] = f[i-2] + f[i-1];
  14.     }
  15.     // 返回目标值
  16.     return f[n];
  17. };

（2）使用场景

上面用动态规划的思想解决了“爬楼梯”的问题，当然我们的目的并不是为了解决这个问题，而是通过这个问题来看动态规划，下面就来重新认识一下动态规划。

上面说过了分支问题，它的核心思想是：把一个问题分解为相互独立的子问题，逐个解决子问题后，再组合子问题的答案，就得到了问题的最终解。

动态规划的思想和“分治”有点相似。不同之处在于，“分治”思想中，各个子问题之间是独立的：比如说归并排序中，子数组之间的排序并不互相影响。而动态规划划分出的子问题，往往是相互依赖、相互影响的。

那什么样的题应该用动态规划来做？要抓以下关键特征：

  • 最优子结构，它指的是问题的最优解包含着子问题的最优解——不管前面的决策如何，此后的状态必须是基于当前状态（由上次决策产生）的最优决策。就这道题来说，f(n)和f(n-1)、f(n-2)之间的关系（状态转移方程）印证了这一点。
  • 重叠子问题，在递归的过程中，出现了反复计算的情况。
  • 无后效性，无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

所以，只要需要解决的问题符合这三个关键特征，就可以使用动态规划来求解。

2. LeetCode 路径问题

（1）不同路径

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

问总共有多少条不同的路径？
示例 1：
数据结构与算法之动态规划篇 - 图2

  1. 输入：m = 3, n = 7
  2. 输出：28

示例 2：

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

示例 3：

  1. 输入：m = 7, n = 3
  2. 输出：28

示例 4：

  1. 输入：m = 3, n = 3
  2. 输出：6

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10

这个题目和爬楼梯问题其实是一样的思路，只不过爬楼梯问题算是一维的问题，而这个问题是一个二维的问题。看到这个问题，我们自然而然的就能想到动态规划。

每一个网格的路径数都和其上侧和左侧的路径数相关，可以得出递推方程：

  1. a[i][j] = a[i - 1][j] + a[i][j - 1]

首先初始化一个m * n 的二维数组，数组的所有节点值都先初始为0，由于最上边一行和最左边一列都是边界，只能有一种走法，所以初始为1。然后根据递推方程求解即可。

  1. /**
  2.  * @param {number} m
  3.  * @param {number} n
  4.  * @return {number}
  5.  */
  6. var uniquePaths = function(m, n) {
  7.     const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
  9.     for(let i = 0; i < m; i++){
  10.         dp[i][0] = 1
  11.     }
  12.     for(let j = 0; j < n; j++){
  13.         dp[0][j] = 1
  14.     }
  16.     for(let i = 1; i < m; i++){ 
  17.         for(let j = 1; j < n; j++){
  18.             dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  19.         }
  20.     }
  21.     return dp[m - 1][n - 1]
  22. };

复杂度分析：

  • 时间复杂度：O(mn)，其中m和n分别是网格的长宽，我们需要两层遍历，所以空间复杂度为O(mn)。
  • 空间复杂度：O(mn)，其中m和n分别是网格的长宽，我们需要一个m * n 的二维数组来存储所有状态，所以所需空间复杂度为O(mn)。

    （2）不同路径 II

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
数据结构与算法之动态规划篇 - 图3
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
数据结构与算法之动态规划篇 - 图4

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

示例 2：
数据结构与算法之动态规划篇 - 图5

  1. 输入：obstacleGrid = [[0,1],[0,0]]
  2. 输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

这道题目和62题不同路径 是一样的思路：动态规划。

不同的是，这个题目中出现了障碍物，所以在遍历的时候需要注意以下两点：

  • 在给第一行和第一列元素设置初始值时，如果遇到网格的值是1，也就是有障碍物的情况，就直接停下来，不需要往前继续遍历了，因为前面就不可能在经过了；
  • 在计算每个网格的路径数时，如果该方格元素是就直接跳过，不需要计算。

以上两点就是本题和62题的不同之处，根据这个思路实现即可。

  1. /**
  2.  * @param {number[][]} obstacleGrid
  3.  * @return {number}
  4.  */
  5. var uniquePathsWithObstacles = function(obstacleGrid) {
  6.     if(!obstacleGrid.length || obstacleGrid[0][0] === 1){
  7.         return 0
  8.     }
  10.     const m = obstacleGrid.length, n = obstacleGrid[0].length
  11.     const dp = new Array(m).fill(0).map(() =>  new Array(n).fill(0))
  13.     for (let i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
  14.         dp[i][0] = 1;
  15.     }
  16.     for (let j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
  17.         dp[0][j] = 1;
  18.     }
  20.     for(let i = 1; i < m; i++){ 
  21.         for(let j = 1; j < n; j++){
  22.             if(obstacleGrid[i][j] === 0){
  23.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  24.             }
  25.         }
  26.     }
  27.     return dp[m - 1][n - 1]
  28. };

复杂度分析：

  • 时间复杂度：O(mn)，其中m和n分别是网格的长宽，我们需要两层遍历，所以空间复杂度为O(mn)。

  • 空间复杂度：O(mn)，其中m和n分别是网格的长宽，我们需要一个m * n 的二维数组来存储所有状态，所以所需空间复杂度为O(mn)。

    （3）最小路径和

    给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
    说明：每次只能向下或者向右移动一步。

    示例 1：
    数据结构与算法之动态规划篇 - 图6

    1. 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
    2. 输出：7
    3. 解释：因为路径 1→3→1→1→1 的总和最小。

    示例 2：

    1. 输入：grid = [[1,2,3],[4,5,6]]
    2. 输出：12

    提示：

  • m == grid.length

  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

对于这道题目，路径的方向只能是从上到下，从左向右。我们可以知道，当前点的路径和都和上一个点的路径和相关，所以这里我们可以使用动态规划来解答。

对于第一行的元素，它只能是左边的元素移动过来的，当前的元素的路径总和关系如下：

  1. grid[i][0] += grid[i - 1][0]

对于第一列的元素，它只能是上边的元素移动过来的，当前的元素的路径总和关系如下：

  1. grid[0][j] += grid[0][j - 1]

对于其他位置的元素，他可以是上边移动过来的，也可以是左边移动过来的，因为要求的是最小路径和，所以我们只需要选取左边和上面的路径和最小值，当前的元素的路径总和关系如下：

  1. grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];

这样，经过遍历之后，每个节点的值就是当前的最小路径和。最后只需要返回右下角元素的值即可。

  1. /**
  2.  * @param {number[][]} grid
  3.  * @return {number}
  4.  */
  5. var minPathSum = function(grid) {
  6.     let m = grid.length, n = grid[0].length
  8.     for(let i = 1; i < m; i++){
  9.         grid[i][0] += grid[i - 1][0]
  10.     }
  11.     for(let j = 1; j < n; j++){
  12.         grid[0][j] += grid[0][j - 1]
  13.     }
  15.     for(let i = 1; i < m; i++){
  16.         for(let j = 1; j < n; j++){
  17.             grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
  18.         }
  19.     }
  20.     return grid[m - 1][n - 1]
  21. }

复杂度分析：

  • 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 grid 的每个元素的值。
  • 空间复杂度：O(1)，这里我们是在原数组的基础上进行的操作，所需的额外的空间为常数。

    （4）三角形最小路径和

    给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

  1. 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
  2. 输出：11
  3. 解释：如下面简图所示：
  4.    2
  5.   3 4
  6.  6 5 7
  7. 4 1 8 3
  8. 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

  1. 输入：triangle = [[-10]]
  2. 输出：-10

提示：

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1

  • -104 <= triangle[i][j] <= 104


    进阶：

  • 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

这道题目和最小路径和那道题的阶梯思路类似，都是使用动态规划来解决。

这里，其实我们并不需要初始化一个数组来保存每一步的状态（每个节点的最小路径值），可以在原数组上进行操作，因为每个节点都只遍历一次，在遍历完之后，我们只需要将当前节点的状态赋值给当前节点即可。

这里同样需要处理两个边界的问题，对于第一列元素，他只能是上面的元素下来的，所以他的状态转移方程是：

  1. triangle[i][j] += triangle[i - 1][j]

对于每一行的最后一位，它只能是上一行的最后一位下来的，所以他的状态转移方程是：

  1. triangle[i][j] += triangle[i - 1][j - 1]

对于其他的元素，可以是其对应序号以及对应序号减一的元素移动下来的，所以他的状态转移方程是：

  1. triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])

最后我们只需要返回最后一行元素的最小值即可，这里我们用…扩展运算符配合Math的min方法求得最后一行的最小值。

  1. /**
  2.  * @param {number[][]} triangle
  3.  * @return {number}
  4.  */
  5. var minimumTotal = function(triangle) {
  6.     const n = triangle.length
  8.     for(let i = 1; i < n; i++){
  9.         for(let j = 0; j <= i; j++){
  10.             if(j === 0){
  11.                 triangle[i][j] += triangle[i - 1][j]
  12.             }else if(j === i){
  13.                 triangle[i][j] += triangle[i - 1][j - 1]
  14.             }else{
  15.                 triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])
  16.             }
  17.         }
  18.     }
  20.     return Math.min(...triangle[n - 1])
  21. };

复杂度分析：

  • 时间复杂度：O(n2)，其中 n 是三角形的行数。
  • 空间复杂度：O(1)。这里我们在原数组的基础上进行的操作，所以所需要的额外的空间为常数。

    3. LeetCode 买卖股票问题

    （1）买卖股票的最佳时机

    给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。

示例 1:

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

示例 2:

  1. 输入: [7,6,4,3,1]
  2. 输出: 0
  3. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

（1）直接遍历
我们需要对股票进行一次买入、一次卖出，卖出在买入之后，并且要计算最大的利润。

这里初始化一个最小值min，和一个最大的结果值max。遍历数组，如果当前数组元素小于最小值民，就更新最小值，始终让其保持最小。如果当前值减去最小值大于最大值，就更新最大值。直到遍历完数组所有的元素，返回最后的结果。

（2）动态规划
对于这道题，我们可以使用动态规划来解决。这里我们只需要进行一次买入卖出。那到最后交易时，可能会有三种状态：

  • dp[0]：一直没有买
  • dp[1]：：到最后只买了一笔，未卖出
  • dp[2]：：到最后只卖了一笔，并卖出

由于第一种状态未进行任何操作，所以可以不用记录。然后我们对后两种状态进行转移：

  • dp[1] = Math.max(dp[1], -prices[i])：前一天也是b1状态或者是没有任何操作，今天买入一笔变成b1状态；
  • dp[2] = Math.max(dp[2], dp[1] + prices[i])：前一天也是s1状态或者是b1状态，今天卖出一笔变成s1状态；

（1）直接遍历

  1. /**
  2.  * @param {number[]} prices
  3.  * @return {number}
  4.  */
  5. var maxProfit = function(prices) {
  6.     let max = 0
  7.     let min = prices[0]
  9.     prices.forEach( item => {
  10.         if(item < min) min = item
  11.         if(item - min > max) max = item - min
  12.     })
  13.     return max
  14. };

复杂度分析：

  • 时间复杂度： O(n)，其中n是数组的长度，我们需要将数组遍历一遍
  • 空间复杂度： O(1)，这里只需要常数空间来储存最小值min和最大结果值max

（2）动态规划

  1. /**
  2.  * @param {number[]} prices
  3.  * @return {number}
  4.  */
  5. var maxProfit = function(prices) {
  6.     let len = prices.length;
  7.     const dp = [0, -prices[0], 0]
  9.     for (let i = 1; i < len; i++) {
  10.         dp[1] = Math.max(dp[1], -prices[i])
  11.         dp[2] = Math.max(dp[2], dp[1] + prices[i])
  12.     }
  13.     return dp[2];
  14. }

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是数组 prices 的长度。
  • 空间复杂度：O(1)。

    （2）买卖股票的最佳时机 II

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

示例 1:

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

示例 2:

  1. 输入: [1,2,3,4,5]
  2. 输出: 4
  3. 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  4.      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
  5.      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

  1. 输入: [7,6,4,3,1]
  2. 输出: 0
  3. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 3 * 10
  • 0 <= prices[i] <= 10

对于这道题目，我们可以使用动态规划来解答。每个点的状态描述：手里有股票或者没股票。

1）dp[i][0]表示：第 i 天手里没股票，至今（第 i 天）的最大收益。第 i 天手里没股票，有两种可能：

  • 昨天也没持有股票：dp[i-1][0]
  • 昨天买了股票，今天卖了: dp[i-1][1] + prices[i]
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

2）dp[i][1]表示：第 i 天手里有股票，至今（第 i 天）的最大收益。第 i 天手里有股票，有两种可能：

  • 昨天也有股票：dp[i-1][1]
  • 昨天卖了，今天买了: dp[i-1][0] - prices[i]
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

最终目标是求出：dp[prices.length-1][0]和dp[prices.length-1][1]的较大者，前者肯定>=后者，求dp[prices.length-1][0]即可。

对于开始：

  • day 0 没买:dp[0][0] = 0

  • day 0 买了:dp[0][1] = -prices[0]

    1. /**
    2. * @param {number[]} prices
    3. * @return {number}
    4. */
    5. function maxProfit(prices) {
    6. const len = prices.length;
    7. if (len < 2) {
    8.   return 0;
    9. };
    10. const dp = new Array(len);
    11. dp[0] = [0, -prices[0]];
    12. for (let i = 1; i < len; i++) {
    13.   dp[i] = new Array(2);
    14.   dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 没有股票
    15.   dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 有股票
    16. }
    17. return dp[len - 1][0];
    18. }

    复杂度分析：

  • 时间复杂度： O(n)，其中 n 为数组的长度。一共有 2n 个状态，每次状态转移的时间复杂度为 O(1)，因此时间复杂度为 O(2n)=O(n)。

  • 空间复杂度：O(n)，我们需要开辟O(n) 空间存储动态规划中的所有状态。

    （3）买卖股票的最佳时机 III

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

示例 1:

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

示例 2：

  1. 输入：prices = [1,2,3,4,5]
  2. 输出：4
  3. 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
  4.      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
  5.      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

  1. 输入：prices = [7,6,4,3,1] 
  2. 输出：0 
  3. 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

  1. 输入：prices = [1]
  2. 输出：0

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105

对于这道题，我们可以使用动态规划来解决。在《买卖股票的最佳时机》中，我们只能进行一次买入卖出。而这道题，我们可以进行至多两次的买入卖出，那到最后交易时，可能会有五种状态：

  • dp[0]：一直没有买
  • dp[1]：到最后只买了一笔，未卖出
  • dp[2]：到最后只卖了一笔，并卖出
  • dp[3]：到最后买了两笔，只卖出一笔
  • dp[4]：到最后买了两笔，两笔都卖出

由于第一种状态未进行任何操作，所以可以不用记录。然后我们对后四种状态进行转移：

  • dp[1] = Math.max(dp[1], -prices[i])：前一天也是b1状态或者是没有任何操作，今天买入一笔变成b1状态；
  • dp[2] = Math.max(dp[2], dp[1] + prices[i])：前一天也是s1状态或者是b1状态，今天卖出一笔变成s1状态；
  • dp[3] = Math.max(dp[3], dp[2] - prices[i])：前一天也是b2状态或者是s1状态，今天买入一笔变成b2状态；

  • dp[4] = Math.max(dp[4], dp[3] + prices[i])：前一天也是s2状态或者是b2状态，今天冒出一笔变成s2状态。

    1. /**
    2. * @param {number[]} prices
    3. * @return {number}
    4. */
    5. function maxProfit(prices) {
    6.   let len = prices.length;
    7.   const dp = [0, -prices[0], -prices[0], 0, 0]
    9.   for (let i = 1; i < len; i++) {
    10.       dp[1] = Math.max(dp[1], -prices[i])
    11.       dp[2] = Math.max(dp[2], dp[1] + prices[i])
    12.       dp[3] = Math.max(dp[3], dp[2] - prices[i])
    13.       dp[4] = Math.max(dp[4], dp[3] + prices[i])
    14.   }
    15.   return dp[4];
    16. };

    复杂度分析：

  • 时间复杂度：O(n)，其中 n 是数组 prices 的长度。

  • 空间复杂度：O(1)。

    （4）买卖股票的最佳时机 IV

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

示例 1：

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

示例 2：

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

提示：

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

在题目《买卖股票的最佳时机》中，我们只能进行一次买入卖出，在题目123《买卖股票的最佳时机 III》中，我们可以进行两次买入卖出操作。而在这道题目中，我们可以进行k次买入卖出操作。这里我们也可以使用动态规划来解答。

每次我们只能进行[1, k]次中的某次交易或不交易，所以可能有2k+1中状态：

  • 无操作，一直没有买
  • dp[0]：到最后只买了一笔，未卖出
  • dp[1]：到最后只卖了一笔，并卖出
  • dp[2]：到最后买了两笔，只卖出一笔
  • dp[3]：到最后买了两笔，两笔都卖出
  • dp[4]：到最后买了三笔，只卖出两笔
  • ······

我们可以枚举一天的所有可能，取现金最大值：

  • 不交易，现金 不变

  • 进行[1, k]的某次交易

    • 买入，现金 -= 当天股票价格

    • 卖出，现金 += 当天股票价格

      1. /**
      2. * @param {number} k
      3. * @param {number[]} prices
      4. * @return {number}
      5. */
      6. var maxProfit = function(k, prices) {
      7. const dp = new Int16Array(k * 2).fill(-prices[0])
      9. for (let i = 0; i < prices.length; i++) {
      10.    for (let j = 0; j < dp.length; j++) 
      11.        {
      12.            dp[j] = Math.max(dp[j], (dp[j - 1] || 0) + (j & 1 ? prices[i] : -prices[i]))
      13.        }
      14. }
      15. return Math.max(0, ...dp) 
      16. };

      复杂度分析：

  • 时间复杂度：O(n * min(n, k))，其中 n 是数组 prices 的长度，即使用双重循环进行动态规划需要的时间。

  • 空间复杂度：O(min(n,k))。

    4. LeetCode 打家劫舍问题

    （1）打家劫舍

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

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

示例 1：

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

示例 2：

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

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

对于这道题目，我们可以使用动态规划来实现。首先来看最简单的两种情况，如果只有一间房屋，那这个屋子就是最高的金额，如果有两间房屋，那不能同时偷，只能偷其中其中金额高的那间，如果大于两间屋子，就要进行讨论了。

  • 如果偷第n个房间，那么就不能偷第n - 1个房间，那么总金额就是前n - 2间屋子能偷到的最高的金额之和；
  • 如果不偷第k间屋，那么能偷到的总金额就是前k - 1个房间的最高总金额。

这两者，我们只要取总金额的较大值即可。

我们可以用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

  1. dp[i]=max(dp[i−2]+nums[i],dp[i−1])

边界条件为：

  • dp[0] = nums[0] ：只有一间房屋，则偷窃该房屋
  • dp[1] = max(nums[0], nums[1])：只有两间房屋，选择其中金额较高的房屋进行偷窃

最终的答案即为 dp[n−1]，其中 n 是数组的长度。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function(nums) {
  6.     const len = nums.length
  7.     if(!len){
  8.         return 0
  9.     }
  11.     const dp = new Array(len + 1)
  12.     dp[0] = 0
  13.     dp[1] = nums[0]
  15.     for(let i = 2; i <= len; i++){
  16.         dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
  17.     }
  18.     return dp[len];
  19. };

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
  • 空间复杂度：O(1)。使用数组只存储前两间房屋的最高总金额，而不需要存储整个数组的结果，因此空间复杂度是 O(1)

    （2）打家劫舍 II

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

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

示例 1：

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

示例 2：

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

示例 3：

  1. 输入：nums = [0]
  2. 输出：0

提示：

  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 1000


    打家劫舍这类问题其实都可以使用动态规划来解答，这个题目和打家劫舍类似，不过就是多了两种情况：

  • 不偷第一家

  • 不偷最后一家

这样就可以分类讨论，当不偷第一家时，就排除到第一家，对其他家进行计算，当不偷最后一家时，就排除掉最后一家，对其他家进行计算。

当前节点的最大值就是当前节点和之前的第二个节点的和与上个节点的值的最大值，这样说可能比较绕，状态转移方程代码：

  1. dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

代码实现：

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function(nums) {
  6.     const len = nums.length
  7.     let res1 = 0, res2 = 0
  8.     if(len === 0) return 0
  9.     if(len === 1) return nums[0]
  11.     const dp = new Array(len)
  13.     // 不偷第一家
  14.     dp[0] = 0
  15.     dp[1] = nums[1]
  16.     for(let i = 2; i <= len - 1; i++){
  17.         dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  18.     }
  19.     res1 = dp[len - 1]
  21.     // 不偷最后一家
  22.     dp[0] = nums[0]
  23.     dp[1] = Math.max(nums[0], nums[1])
  24.     for(let i = 2; i <= len - 2; i++){
  25.         dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  26.     }
  27.     res2 = dp[len - 2]
  28.     return Math.max(res1, res2)
  29. };

复杂度分析：

  • 时间复杂度：O(n)，其中n是数组的长度，我们需要遍历两次数组；
  • 空间复杂度：O(n)，其中n是数组的长度，我们需要初始化一个长度为n的数组来保存当前节点的状态。

    （3）打家劫舍 III

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

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

  1. 输入: [3,2,3,null,3,null,1]
  2.      3
  3.     / \
  4.    2   3
  5.     \   \ 
  6.      3   1
  7. 输出: 7 
  8. 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

  1. 输入: [3,4,5,1,3,null,1]
  2.      3
  3.     / \
  4.    4   5
  5.   / \   \ 
  6.  1   3   1
  7. 输出: 9
  8. 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

对于这道题目，可以使用动态规划来解答。

对于二叉树，每个节点都有两种状态，选中或者不选中，我们可以使用深度优先遍历来遍历这棵二叉树：

  • 当节点被选中时，它的左右孩子都不能被选中，所以最大值就是：node.val + left[1] + right[1]；
  • 当节点不被选中时，它的左右子孩子可以选中也可以不选中，所以最大值就是：Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

最后返回左右子树中最大值即可。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number}
  12.  */
  13. var rob = function(root) {
  14.     const dfs = (node) => {
  15.         if (node === null) {
  16.             return [0, 0];
  17.         }
  18.         const left = dfs(node.left);
  19.         const right = dfs(node.right);
  21.         const select = node.val + left[1] + right[1];
  22.         const notSelect = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
  23.         return [select, notSelect];
  24.     }
  25.     const res = dfs(root)
  26.     return Math.max(res[0], res[1])
  27. };

复杂度分析：

  • 时间复杂度：O(n)，对二叉树进行了一次后序遍历，所以时间复杂度是 O(n)；
  • 空间复杂度：O(n)，递归栈空间的使用代价是 O(n)。

    5. LeetCode 回文串问题

    （1）回文子串

    给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

  1. 输入："abc"
  2. 输出：3
  3. 解释：三个回文子串: "a", "b", "c"

示例 2：

  1. 输入："aaa"
  2. 输出：6
  3. 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：输入的字符串长度不会超过 1000 。

这个题目最直接的方法就是使用暴力循环来解决，遍历每一种可能，具体思路如下：

  • 首先，根据题目，我们可以看出，每个元素自身也算是一个回文子串，所以要将字符串的长度加进去
  • 定义一个函数用来检测字符串是否是回文串
  • 两层遍历字符串，截取字符串的所有的子串，并判断其是否是回文串

复杂度分析：

  • 时间复杂度为O(n2)，需要两层遍历。

  • 空间复杂度为O(1)

    1. /**
    2. * @param {string} s
    3. * @return {number}
    4. */
    5. var countSubstrings = function(s) {
    6.   let count = s.length
    7.   let len = s.length
    8.   for(let i = 0; i < len; i++){
    9.       for(let j = i + 1; j < len; j++){
    10.           let temp = s.substr(i, j-i+1)
    11.           if(isSub(temp)){
    12.               count++
    13.           }
    14.       }
    15.   }
    16.   return count
    17. };
    18. const isSub = str => {
    19.       let a = 0
    20.       let b = str.length - 1
    21.       while(a <= b){
    22.           if(str[a] !== str[b]){
    23.               return false
    24.           }
    25.           a++
    26.           b--
    27.       }
    28.       return true
    29.   }

    （2）最长回文子串

    给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
    示例 1：

    1. 输入: "babad"
    2. 输出: "bab"
    3. 注意: "aba" 也是一个有效答案。

    示例 2：

    1. 输入: "cbbd"
    2. 输出: "bb"

    这里使用两种方法来解答这个问题：
    （1）方法一：中心扩展法
    中心扩展法的思想就是枚举出可能出现的回文串的中心，从这个中心位置尽可能的向两边扩散出去，得到一个回文串，具体实现步骤如下：

  • 选取对称中心（奇数长度的字符串为中心两个字符的中间，偶数长度的字符串中心为中间的字符）

  • 通过对比扩展之后得出的两种组合较大的回文子串长度
  • 对比之前的长度，判断是否更新起始的位置
  • 遍历完之后，根据起始位置，截取最长回文子串

代码实现：

  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  5. var longestPalindrome = function(s) {
  6.     if(s == null || s.length <1){
  7.         return ''
  8.     }
  9.     let start = 0
  10.     let end = 0
  11.     // 定义中心扩展的方法
  12.     const fn = (s,left,right) => {
  13.         while(left >=0 && right< s.length && s[left] === s[right]){
  14.             left--
  15.             right++
  16.         }
  17.         return right - left -1
  18.     }
  19.     // 遍历字符串
  20.     for(let i = 0; i<s.length; i++){
  21.         const len1 = fn(s, i, i)
  22.         const len2 = fn(s, i, i+1)
  23.         const len = Math.max(len1, len2)
  24.         // 判断起始位置是否更新
  25.         if(len > end - start){
  26.             start = i- Math.floor((len-1)/2)
  27.             end = i+ Math.floor(len/2)
  28.         }
  29.     }
  30.     return s.substring(start, end+1)
  31. };

复杂度分析：

  • 时间复杂度：O(n2)，枚举“中心位置”时间复杂度为 O(n)，从“中心位置”扩散得到“回文子串”的时间复杂度为 O(n)，因此时间复杂度是 O(n2)。
  • 空间复杂度：O(1)，这里只用到了两个常数临时变量start、end，因此空间复杂度为O(1)。

（2）方法二：动态规划
解决这类问题的核心思想就是两个字“延伸”，具体来说

  • 如果一个字符串是回文串，那么在它左右分别加上一个相同的字符，那么它一定还是一个回文串
  • 如果在一个不是回文字符串的字符串两端添加任何字符，或者在回文串左右分别加不同的字符，得到的一定不是回文串

事实上，上面的分析已经建立了大问题和小问题之间的关联，因为我们可以建立动态规划模型。可以用 dp[i][j] 表示 s 中从 i 到 j（包括 i 和 j）是否可以形成回文，状态转移方程只是将上面的描述转化为代码即可：

  1. if (s[i] === s[j] && dp[i + 1][j - 1]) {
  2.   dp[i][j] = true;
  3. }

其中：

  • s[i] === s[j]：说明当前中心可以继续扩张，进而有可能扩大回文串的长度
  • dp[i+1][j-1]：true，说明s[i,j]的子串s[i+1][j-1]也是回文串，其中，i是从最大值开始遍历的，j是从最小值开始遍历的

总结一下，使用动态规划的具体实现步骤如下：

  • 确定dp[i][j]是否是回文数，只需要dp[i+1][j-1]是回文数并且s[i] === s[j]即可。
  • 长度为0或1的回文传需要特殊处理，即j-i < 2;
  • 因为知道dp[i]需要先知道dp[i+1]，所以i需要从大到小开始遍历
  • 因为知道dp[j]需要先知道dp[j-1]，所以j需要从小到大开始遍历

代码实现：

  1.  /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  5. // 扩展中心
  6. var longestPalindrome = function(s) {
  7.    let res = '';
  8.     let n = s.length;
  9.     let dp = Array.from(new Array(n), () => new Array().fill(0));
  11.     for(let i = n-1; i >=0; i--) {
  12.         for(let j = i; j < n; j++) {
  13.             dp[i][j] = s[i] === s[j] && ( j - i < 2 || dp[i+1][j-1])
  14.             if(dp[i][j] && j - i + 1 > res.length) {
  15.                 res = s.substr(i,j - i + 1);
  16.             }
  17.         }
  18.     }
  19.     return res;
  20. }

复杂度分析：

  • 时间复杂度：O(n2)，其中 n是字符串的长度。动态规划的状态总数为 O(n2)，对于每个状态，需要转移的时间为 O(1)。

  • 空间复杂度：O(n2)，即存储动态规划状态需要的空间。

    （3）最长回文子序列

    给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

    示例 1:

    1. 输入: "bbbab"
    2. 输出: 4
    3. 一个可能的最长回文子序列为 "bbbb"。

    示例 2:

    1. 输入: "cbbd"
    2. 输出: 2
    3. 一个可能的最长回文子序列为 "bb"。

    提示：

  • 1 <= s.length <= 1000

  • s 只包含小写英文字母

对于这种回文子串的问题，我们可以考虑能否使用动态规划来求解。

这里我们尝试使用动态规划来解答，初始化一个dp二维数组来保存子串的长度，dp[i][j]表示s中的第i个字符到第j个字符组成的子串中，最长的回文序列的长度。

下面最重要的就是找出状态转移方程：

  • 如果字符串s的第i个和第j个字符相同：f[i][j] = f[i + 1][j - 1] + 2
  • 如果字符串s的第i个和第j个字符不相同：f[i][j] = max(f[i + 1][j], f[i][j - 1])

这里需要注意遍历时的顺序，i是从最后一个字符开始遍历的，j是从i+1开始向后遍历，这样就能保证每个子问题都计算好了。最后只要返回dp[0][len-1]即可。

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var longestPalindromeSubseq = function(s) {
  6.     let len = s.length;
  8.     let dp = new Array(len)
  9.     for (let i = 0; i < len; i++) {
  10.         dp[i] = new Array(len).fill(0);
  11.     }
  13.     for (let i = len - 1; i >= 0; i--) {
  14.         dp[i][i] = 1;
  15.         for (let j = i+1; j < len; j++) {
  16.             if (s[i] === s[j]) {
  17.                 dp[i][j] = dp[i+1][j-1] + 2;
  18.             } else {
  19.                 dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
  20.             }
  21.         }
  22.     }
  23.     return dp[0][len-1];
  24. };

复杂度分析：

  • 时间复杂度：O(n2)，其中n是字符串的长度，我们需要一个双层的遍历；
  • 空间复杂度：O(n2)，其中n是字符串的长度，我们需要初始化一个二维数组。

    6. LeetCode 子序列问题

    （1）最大子序和

    给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    示例:
    1. 输入: [-2,1,-3,4,-1,2,1,-5,4]
    2. 输出: 6
    3. 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
    进阶:
    如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

动态规划求解：
通常我们遍历子串或者子序列有三种遍历方式

  • 以某个节点为开头的所有子序列: 如 [a]，[a, b]，[ a, b, c] … 再从以 b 为开头的子序列开始遍历 [b] [b, c]。
  • 根据子序列的长度为标杆，如先遍历出子序列长度为 1 的子序列，在遍历出长度为 2 的 等等。
  • 以子序列的结束节点为基准，先遍历出以某个节点为结束的所有子序列，因为每个节点都可能会是子序列的结束节点，因此要遍历下整个序列，如: 以 b 为结束点的所有子序列: [a , b] [b] ，以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。

其中，第一种方式通常会使用暴力方法的求解，第二种方式在上面第五题已将用到过了，重点是第三种方式：因为可以产生递推关系, 采用动态规划时, 经常通过此种遍历方式, 如背包问题、最大公共子串 , 这里的动态规划解法也是以先遍历出以某个节点为结束节点的所有子序列的思路。

代码实现：

  1. var maxSubArray = function(nums) {
  2.     let sum = 0, res = nums[0]
  3.     for(let num of nums){
  4.         sum > 0 ? sum += num : sum = num
  5.         res = Math.max(sum, res)
  6.     }
  7.     return res
  8. };

复杂度分析：

  • 时间复杂度：O(n)，其中 n 为 nums 数组的长度，只需要遍历一遍数组即可求得答案。
  • 空间复杂度：O(1)，只需要常数空间存放若干变量。

    （2）最长递增子序列

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

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

示例 1：

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

示例 2：

  1. 输入：nums = [0,1,0,3,2,3]
  2. 输出：4

示例 3：

  1. 输入：nums = [7,7,7,7,7,7,7]
  2. 输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶：

  • 你可以设计时间复杂度为 O(n2) 的解决方案吗？
  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

碰到子序列的问题，我们最容易想到的就是动态规划。首先初始化一个数组dp来保存每个子问题的最优解，dp[i]表示数组前n的元素的最长连续子序列，最后返回所有子序列中最长的序列就可以了。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var lengthOfLIS = function(nums) {
  6.     const n = nums.length
  7.     if(!n){
  8.         return 0
  9.     }
  11.     let dp = new Array(n).fill(1)
  12.     for(let i = 1; i < n; i++){
  13.         for(let j = 0; j < i; j++){
  14.             if(nums[i] > nums[j]){
  15.                 dp[i] = Math.max(dp[i], dp[j] + 1)
  16.             }
  17.         }
  18.     }
  19.     return Math.max(...dp)
  20. };

复杂度分析：

  • 时间复杂度：O(n)，其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n) 的时间遍历dp[0…i−1] 的所有状态，所以总时间复杂度为 O(n)。
  • 空间复杂度：O(n)，需要额外使用长度为 n 的 dp 数组。

    （3）乘积最大的子数组

    给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

    示例 1:
    1. 输入: [2,3,-2,4]
    2. 输出: 6
    3. 解释: 子数组 [2,3] 有最大乘积 6。
    示例 2:
    1. 输入: [-2,0,-1]
    2. 输出: 0
    3. 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
    对于这道题目，我们可以使用动态规划来解答。

我们只需要在遍历数组时，不断更新最大值即可，这个过程中，我们需要维护两个值：

  • max，当前的最大值，将当前的值与当前的值和之前的最大值的乘积进行对比，保存最大值
  • min，当前的最小值，将当前的值与当前的值和之前的最小值的乘积进行对比，保存最小值

我们这里求的是最大值，那为啥还要保存最小值呢？这是因为数组中可能会有负数，当当前的值是负数时，与之前的值相乘就会导致最大值和最小值交换，所以我们需要维护一个最大值和一个最小值。然后不断使用当前的最大值保存为结果，最后返回结果即可。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var maxProduct = function(nums) {
  6.     let res = -Infinity, max = 1, min = 1;
  8.     for(let i = 0; i < nums.length; i++){
  9.         if(nums[i] < 0){
  10.             let temp = max
  11.             max = min
  12.             min = temp
  13.         }
  14.         max = Math.max(nums[i], nums[i] * max)
  15.         min = Math.min(nums[i], nums[i] * min)
  17.         res = Math.max(res, max)
  18.     }
  19.     return res
  20. };

复杂度分析：

  • 时间复杂度：O(n)，我们需要遍历一遍数组，所以时间复杂度为O(n)；

  • 空间复杂度：O(1)，这里我们需要的额外空间为常数级，所以空间复杂度为O(1)。

    （4）最长重复子数组

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

    示例：

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

    提示：

  • 1 <= len(A), len(B) <= 1000

  • 0 <= A[i], B[i] < 100

对于这道题目，我们可以使用动态规划来解决。动态规划就是要保持上一个状态和下一个状态有关系，并且是连续的。这里的子数组就相当于子串，是连续的。

这里我们初始化一个dp数组保存当前的最大连续值，dp[i][j]表示数组A的前i个元素和数组B的前j个元素组成的最长公共子数组的长度。

在遍历数组时：

  • 如果当前的两个元素的值相等，也就是A[i] === B[j]，则说明当前的元素可以构成公共子数组，所以让前一个元素的最长公共子数组的长度加一，此时的状态转移方程是：dp[i][j] = dp[i - 1][j - 1] + 1；
  • 如果当前的两个元素的值不相等，所以此时的dp值保存为0（初始化为0）。

在遍历的过程中，不断更新最长公共子序列最大值。

  1. /**
  2.  * @param {number[]} A
  3.  * @param {number[]} B
  4.  * @return {number}
  5.  */
  6. var findLength = function(A, B) {
  7.     const m = A.length, n = B.length;
  9.     let dp = new Array(m + 1)
  10.     for (let i = 0; i <= m; i++) { 
  11.         dp[i] = new Array(n + 1).fill(0);
  12.     }
  14.     let res = 0
  16.     for(let i = 1; i <= m; i++){
  17.         for(let j = 1; j <= n; j++){
  18.             if(A[i - 1] === B[j - 1]){
  19.                 dp[i][j] = dp[i - 1][j - 1] + 1
  20.             }
  21.             res = Math.max(dp[i][j], res)
  22.         }
  23.     }
  24.     return res
  25. };

复杂度分析：

  • 时间复杂度：O(mn)，其中m和n分别是A和B两个数组的长度，这里我们需要两层遍历两个数组。
  • 空间复杂度：O(mn)，其中m和n分别是A和B两个数组的长度，我们需要初始化一个dp二维数组来保存当前的最长公共子数组的长度。

    7. LeetCode 其他问题

    （1）接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
数据结构与算法之动态规划篇 - 图7

  1. 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
  2. 输出：6
  3. 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

  1. 输入：height = [4,2,0,3,2,5]
  2. 输出：9

提示：

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

看到这道题，我们自然而然的可以想到木桶效应，每根柱子上的雨水的深度取决于它两侧最高的柱子中较短的那根柱子的长度。

  • 如果这个较短的柱子的长度大于当前柱子，那么雨水的深度就是较短的柱子减去当前柱子的长度；
  • 如果这个较短的柱子的长度小于等于当前柱子，那么雨水的深度就是0。

对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。

最直接的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。使用动态规划的方法，可以在 O(n)的时间内预处理得到每个位置两边的最大高度。

  1. /**
  2.  * @param {number[]} height
  3.  * @return {number}
  4.  */
  5. var trap = function(height) {
  6.     let len = height.length, sum = 0
  7.     for(let i = 0; i < len - 1; i++){
  8.         // 计算当前柱子左侧的最大值
  9.         let left = 0
  10.         for(let j = i - 1; j >= 0; j--){
  11.             left = Math.max(height[j], left)
  12.         }
  13.         // 计算当前柱子右侧的最大值
  14.         let right = 0
  15.         for(let j = i + 1; j < len; j++){
  16.             right = Math.max(height[j],right)
  17.         }
  18.         // 计算当前柱子能接的雨水量
  19.         if(min > height[i]){
  20.             sum += Math.min(left, right) - height[i]
  21.         }
  22.     }
  23.     return sum
  24. };

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是数组 height 的长度。需要遍历两次height数组；
  • 空间复杂度：O(1)。

    （2）爬楼梯

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

注意： 给定 n 是一个正整数。
示例 1：

  1. 输入： 2
  2. 输出： 2
  3. 解释： 有两种方法可以爬到楼顶。
  4. 1.  1 阶 + 1 阶
  5. 2.  2 阶

示例 2：

  1. 输入： 3
  2. 输出： 3
  3. 解释： 有三种方法可以爬到楼顶。
  4. 1.  1 阶 + 1 阶 + 1 阶
  5. 2.  1 阶 + 2 阶
  6. 3.  2 阶 + 1 阶

看到这个题目，我们应该想到的就是动态规划，将一个大问题分解成多个子问题。首先来看：

  • 第一级台阶：1种方法
  • 第二级台阶：2种方法
  • 第n级台阶：从第n-1级台阶爬一级，或从第n-2级台阶爬2级

所以可以得出递推公式：f(n) = f(n−1) + f(n−2)
这样，我们就可以通过递归完成计算。

上面这种普通递归很显然，有很多的重复计算，所以，我们可以将每次计算的结果进行保存，以便下次计算时直接使用。

普通递归：

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var climbStairs = function(n) {
  6.     const dp = []
  7.     dp[0] = 1
  8.     dp[1] = 1
  9.     for(let i = 2; i <= n; i ++){
  10.         dp[i] = dp[i - 1] + dp[i - 2]
  11.     }
  12.     return dp[n]
  13. };

记忆递归：

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var climbStairs = function(n) {
  6.     let a = 1, b = 1, res = 1;
  7.     for (let i = 1; i < n; i++) {
  8.         a = b
  9.         b = res
  10.         res = a + b
  11.     }
  12.     return res
  13. };

普通递归复杂度分析：

  • 时间复杂度：O(n2)，递归树的深度为n，所以时间复杂度为O(n2)；
  • 空间复杂度：O(n)，这里需要初始化一个数组用来保存每一层台阶的方法数，有n个数，所以空间复杂度为O(n)；

记忆递归复杂度分析：

  • 时间复杂度：O(n)，需要循环执行n次，所以时间复杂度为O(n)；

  • 空间复杂度：O(1)，这里只用了常数个变量作为辅助空间，所以空间复杂度为 O(1)；

    （3）最大正方形

    在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

    示例 1：
    数据结构与算法之动态规划篇 - 图8

    1. 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    2. 输出：4

    示例 2：
    数据结构与算法之动态规划篇 - 图9

    1. 输入：matrix = [["0","1"],["1","0"]]
    2. 输出：1

    示例 3：

    1. 输入：matrix = [["0"]]
    2. 输出：0

    提示：

  • m == matrix.length

  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 '0' 或 '1'

对于这道题目，可以使用动态规划来解决，这里我们需要初始化与一个dp数组，dp[i][i]表示以 (i, j)为右下角，且只包含 1 的正方形的边长最大值。我们只需要遍历这个二维矩阵，计算机每个dp的值，选出最大值，即正方形的最大边长，最后返回这个正方形的面积即可。

计算dp的每个值有以下规则：

  • 如果当前的值为0，此时该点不存在于正方形中，直接给dp[i][j]赋值为0；
  • 如果当前的值为1，dp[i][j]的值由其上、左、左上的三个值的最小值决定，所以其状态转移方程是：
    1. dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    除此之外，我们还需要考虑二维矩阵的最左边一列和最上面一行，如果值是1，就直接将dp[i][j]赋值为1。

代码实现：

  1. /**
  2.  * @param {character[][]} matrix
  3.  * @return {number}
  4.  */
  5. var maximalSquare = function(matrix) {
  6.     const m = matrix.length, n = matrix[0].length
  7.     let res = 0
  8.     if(!matrix || m === 0 || n === 0){
  9.         return 0
  10.     }
  12.     let dp = new Array(m)
  13.     for(let i = 0; i < m; i++){
  14.         dp[i] = new Array(n).fill(0)
  15.     }
  17.     for(let i = 0; i < m; i++){
  18.         for(let j = 0; j < n; j++){
  19.             if(matrix[i][j] === '1'){
  20.                 if(i === 0 || j === 0){
  21.                     dp[i][j] = 1
  22.                 }else{
  23.                     dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
  24.                 }
  25.                 res = Math.max(dp[i][j], res)
  26.             }
  27.         }
  28.     }
  29.     return res * res
  30. };

复杂度分析：

  • 时间复杂度：O(mn)，其中 m 和 n 是二维矩阵的行数和列数。我们需要遍历二维矩阵中的每个元素来计算 dp 的值。
  • 空间复杂度：O(mn)，其中 m 和 n 是二维矩阵的行数和列数。我们创建了一个和原始矩阵大小相同的数组 dp 来保存当前正方形的最大边长。