背题家记录本

# 动态规划

# 斐波那契数列

Wiki Link (opens new window)

斐波那契数列（意大利语 (opens new window)：Successione di Fibonacci），又译为菲波拿契数列、菲波那西数列、斐氏数列、黄金分割数列。

在数学 (opens new window)上，斐波那契数列是以递归 (opens new window)的方法来定义：

  • F0 = 0
  • F1 = 0
  • Fn = Fn-1 + Fn-2 (n≧2）

用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是：

0 (opens new window), 1 (opens new window), 1 (opens new window), 2 (opens new window), 3 (opens new window), 5 (opens new window), 8 (opens new window), 13 (opens new window), 21 (opens new window), 34 (opens new window), 55 (opens new window), 89 (opens new window), 144 (opens new window), 233 (opens new window)……（OEIS (opens new window)中的数列A000045 (opens new window)）

特别指出：0 (opens new window)不是第一项，而是第零项。

# 70. 爬楼梯 (opens new window)

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

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

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

示例 1：

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

题解：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  // 存储爬到每层楼梯的方式数，下标0代表第一层
  const dp = []
  dp[0] = 1// 第一层有一种方式 1
  dp[1] = 2// 第二层有两种方式 11 & 2
  for (let i = 2; i < n; i++) {
    // 后面的每层，都是等于前两层的数相加
    // 因为假设现在第三层，那么如果是从第一层过来，只有一种方式（到达第一层的方式数+2步）
    // 如果是从第二层过来，只有两种方式（到达第二层的方式数+2步）
    dp[i] = dp[i - 2] + dp[i - 1]
  }
  return dp[n - 1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

常量优化算法：

var climbStairs = function (n) {
  const dp = []
  let dptwo = 1
  let dpone = 2
  // 注意ans初始为n，因为 n<=2 的时候不会进循环
  let ans = n
  for (let i = 2; i < n; i++) {
    ans = dpone + dptwo
    dptwo = dpone
    dpone = ans
  }
  return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 198. 打家劫舍 (opens new window)

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

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

示例 1：

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

题解：

dp 内每一位存放走到当前这步能盗取的最大值

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  // 空返回 [0]
  if (nums.length === 0) return 0
  // dp 内每一位存放走到当前这步能盗取的最大值
  let dp = []
  dp[0] = nums[0]
  // 第二位取前两位最大值
  dp[1] = Math.max(dp[0], nums[1])
  for (let i = 2; i < nums.length; i++) {
    // 偷的话取dp[i - 2] + nums[i],不偷的话取dp[i-1]
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
  }
  return dp[nums.length - 1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

示例 1：

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

示例 2：

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

示例 3：

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

# 213. 打家劫舍 II (opens new window)

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

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

示例 1：

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

示例 2：

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

示例 3：

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

题解：

分别掐头去尾两次 dp

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {

  // 处理 空 len==1 ||2
  if (nums.length === 0) return 0
  if (nums.length === 1 || nums.length === 2) return Math.max(...nums)

  function check(arr) {
    let dp = []
    dp[0] = arr[0]
    dp[1] = Math.max(dp[0], arr[1])
    for (let i = 2; i <= arr.length - 1; i++) {
      dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i])
    }
    return dp[dp.length - 1]
  }
  // 掐头去尾
  const arr1 = nums.slice()
  const arr2 = nums.slice()
  arr1.pop()
  arr2.shift()

  return Math.max(check(arr1), check(arr2))
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 337. 打家劫舍 III (opens new window)

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
1
2
3

题解

每个节点 都可以跳 或者不跳 当前节点选 等于左右都不选 当前不选 等于左右分别选或者不选的最大值相加

那么计算的时候 需要知道子节点的两个情况的值 则需要从下往上获取 保证能拿到到这个节点的最优解

树的dp,先确定先中后序遍历位置,再确定推导关系,本题中由于需要左右子树的值,所以选择后序遍历

/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
    // 每个节点 都可以跳 或者不跳 当前节点选 等于左右都不选 当前不选 等于左右分别选或者不选的最大值相加
    // 那么计算的时候 需要知道子节点的两个情况的值 需要从下往上获取 保证能拿到到这个节点的最优解
    const dfs = (node) => {
        if (!node) return [0, 0]
        const l = dfs(node.left)
        const r = dfs(node.right)

        return [(l[1]) + (r[1]) + node.val, Math.max(l[0], l[1]) + Math.max(r[0], r[1])]
    }
    const res = dfs(root)

    return Math.max(...res)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 信封错排⭐ (opens new window)

假设有5封信放入5个信箱，问：有多少种方案是5个信封全部没有放入对应的信箱中 如：[1,2,3] 有两种方案：[2,3,1] [3,1,2]

题解：

首先要知道 dp[x] 的意思是：有x封信，每个信都有一个自己不能放进去的信箱的情况下的错排情况！

  1. 假设 信 i 放进了信封 j，信 j 放进了信封 k
  2. 首先 信 i 除了信封 i 不能放，其他都可以，有 (i-1) 种放法
  3. 假如 k == i ，那么 信 j 就是放进了 信封 i，剩下 (n-2) 封信有 dp[i-2] 种放的方式【因为这 n-2 封信都有一个对应不能放的信箱，符合一开始我们说的概念】
  4. 假如 k !== i，那么此时 信 k 可以把信箱 i 看作是自己的对应的不能放的信箱，那么此时就是有 (n-1) 封信满足条件，所以此时是 dp[i-1]

最后抽出的公式：

image

var findDerangement = function (n) {
  // 0的时候我们设置为1，方便后面2的求解
  // D(n) = (n-1) [D(n-2) + D(n-1)]
  let dp = [0, 0, 1] //特殊记忆一下
  for (let i = 3; i <= n; i++) {
    dp[i] = (i - 1) * (dp[i - 2] + dp[i - 1])
  }
  return dp[n]
};
console.log(findDerangement(3))
1
2
3
4
5
6
7
8
9
10

# 矩阵路径

# 64. 最小路径和 (opens new window)

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明： 每次只能向下或者向右移动一步。

示例 1：

img

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

示例 2：

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

提示：

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

题解：

到每个格子，都只能从上面或者左面进来

但是第一行和第一列特殊，他们一个只能从左边进一个只能从上面进

为了避免越界等情况，我们可以先把第一行和第一列的全部先算出来，然后再遍历其他值，grid 的每个格子的值都变成到当前格子的最短路径长度

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  // m 列 n 行
  let m = grid[0].length, n = grid.length
  // “到”每个格子，都只能从上面或者左面进来
  // 但是第一行和第一列特殊，他们一个只能从左边进一个只能从上面进
  // 计算第一行
  for (let i = 1; i < m; i++) {
    grid[0][i] += grid[0][i - 1] 
  }
  // 计算第一列
  for (let i = 1; i < n; i++) {
    grid[i][0] += grid[i - 1][0] 
  }
  // 现在开始循环其他的值
  for (let x = 1; x < n; x++) {
    for (let y = 1; y < m; y++) {
      grid[x][y] += Math.min(grid[x - 1][y], grid[x][y - 1])
    }
  }
  return grid[n - 1][m - 1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 62. 不同路径 (opens new window)

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

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

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

示例 1：

img

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

题解：

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  let dp = Array.from({ length: n }, () => new Array(m))
  dp[0][0] = 1
  for (let i = 1; i < m; i++) {
    dp[0][i] = 1
  }

  for (let i = 1; i < n; i++) {
    dp[i][0] = 1
  }

  for (let x = 1; x < n; x++) {
    for (let y = 1; y < m; y++) {
      dp[x][y] = dp[x][y - 1] + dp[x - 1][y]
    }
  }

  return dp[n - 1][m - 1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 数组区间

# 303. 区域和检索 - 数组不可变 (opens new window)

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
1
2
3
4
5
6
7
8
9
10
11

题解：

  1. dp 在构造函数中做，这样不用每次调用 sumRange 都处理
  2. 假设 nums:[1,2,3,4] ，那么 dp:[1,2,6,10] ，求区间就是个差值 this.dp[j] - this.dp[i - 1])，注意一下 下标 0 就行
/**
 * @param {number[]} nums
 */
var NumArray = function (nums) {
  const dp = []
  dp[0] = nums[0]

  for (let i = 1; i <= nums.length - 1; i++) {
    dp[i] = dp[i - 1] + nums[i]
  }
  this.dp = dp
};

/** 
 * @param {number} i 
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function (i, j) {
  return this.dp[j] - (i == 0 ? 0 : this.dp[i - 1])
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(i,j)
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 413. 等差数列划分 (opens new window)

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
1
2
3

以下数列不是等差数列。

1, 1, 2, 5, 7
1

数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。

如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

题解：

dp 存到每个位置为止的等差数列数量，更像是找规律题

可以用常数优化

DP

/**
 * @param {number[]} A
 * @return {number}
 */
var numberOfArithmeticSlices = function (A) {
  if(!A.length) return 0
  const dp = []
  dp[0] = dp[1] = 0
  for (let i = 2; i < A.length; i++) {
    let count = dp[i - 1]
    let j = i
    while (A[j] - A[j - 1] === A[j - 1] - A[j - 2]) {
      count++
      j--
    }
    dp[i] = count
  }
  return dp[A.length - 1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

优化为常数

var numberOfArithmeticSlices = function (A) {
  let ans = 0
  for (let i = 2; i < A.length; i++) {
    let j = i
    while (A[j] - A[j - 1] === A[j - 1] - A[j - 2]) {
      ans++
      j--
    }
  }
  return ans
};
1
2
3
4
5
6
7
8
9
10
11

# 分割整数

dp 的每一位都是存那一位数的答案值。注意当前数和 dp 中的数的关系。

# 343. 整数拆分 (opens new window)

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

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
1
2
3

示例 2:

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

题解：

dp 用来存储每一个数的结果最大值，初始值给 0 ，我们每次只把他拆分成两部分，一个是逐渐增加的整数 j，还有一个是根据选择，如果不拆分，也就是两个数相乘，那就直接乘积，否则是 j*dp[i-j] ，获取剩下的数的最大乘积。然后相乘。

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function (n) {
  const dp = []
  dp[2] = 1

  for (let i = 3; i <= n; i++) {
    dp[i]=0
    for (let j = 1; j <= i - j; j++) {
      dp[i] = Math.max(j * (i - j), j * dp[i - j], dp[i])
    }
  }
  return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 279. 完全平方数⭐ (opens new window)

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

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

示例 1：

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

题解：

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  // dp 存储每位数最多拆出的平方数个数
  let dp = [0]
  for (let i = 1; i <= n; i++) {
    // 最坏的情况是全部拆成1+1+1...
    dp[i] = i
    for (let j = 1; i - j ** 2 >= 0; j++) {
      /**
       * 假设现在是 i=8
       * 拆出 一个1(1*1)，剩下7，那么这次就总共拆成 1+dp[7]个
       * 拆出 一个4(2*2)，剩下4，那么这次就总共拆成 1+dp[4]个
       * 依次类推，拆出 9(3*3)，超过8了，退出
       * 注意上面的 1+dp[x] 的这个1，指的是你拆出了 “1”个平方数，是“个数”
       */
      dp[i] = Math.min(1 + dp[i - j ** 2], dp[i])
    }
  }
  return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这题在 BFS 中也做到过，回顾一下：

var numSquares = function (n) {
  let level = 0
  let queue = [n] // 存放待处理值
  let visited = new Set([n]) // 存放已经计算过的值

  while (queue.length !== 0) {
    level++
    let len = queue.length
    while (len--) {
      let now = queue.shift()
      /**
       * 这里的思路：
       * 每一层用当前值循环减去从1开始的平方数
       * 减下来的值 temp 如果是 0 ，说明已经结束
       * 如果不为 0 ，说明还需要再减平方数，所以把这些 temp 塞进 queue
       * 但是注意，如果这个 temp 已经访问过，那么再遇到的时候就不要访问了，因为那时候肯定不是最短路径
       * 比如 13 ，在 13-1*1-2*2=8,这是第三层遇到了8，
       * 然后在 13-2*2-1*1=8 又遇到了8,
       * 这种重复值层数越高就可能越多，所以用 visited 去重
       * 
       * 为什么用 level 来决定结果？
       * 因为每减一次，不管你减多少，都肯定减去了一个平方数
       */
      for (let i = 1; i ** 2 <= now; i++) {
        let temp = now - i ** 2
        if (temp === 0) {
          return level
        }
        if (!visited.has(temp)) {
          visited.add(temp)
          queue.push(temp)
        }
      }
    }
  }
  return level
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 91. 解码方法 (opens new window)

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1
'B' -> 2
...
'Z' -> 26
1
2
3
4

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。

给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
1
2
3

示例 2：

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
1
2
3

题解：

dp 用来记录到那一位数时的组合数，这就是跳台阶问题，假设我当前是 i 位，那么我有可能是从 i-1 位来的，也有可能是从 i-2 位来的，那么 dp[i] 就等于是 dp[i-1]+dp[i-2]

另外注意一下限制条件处理就好了。

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
  // String.fromCharCode((65+0))
  //  开头0返回
  if (s.startsWith("0")) return 0

  let dp = new Array(s.length + 1).fill(0)
  dp[0] = 1
  dp[1] = 1

  for (let i = 2; i <= s.length; i++) {
    let a = +s.slice(i - 1, i), b = +s.slice(i - 2, i)
    if (a > 0) {
      dp[i] += dp[i - 1]
    }
    if (b >= 10 && b <= 26) {
      dp[i] += dp[i - 2]
    }
  }
  return dp[s.length]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 最长递增子序列

# 300. 最长递增子序列 (opens new window)

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

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

示例 1：

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

题解：

数组：[4,10,4,3,8,9]

dp：[1,2,1,1,2,3]

dp 存储以这一位数作为子序列的结束时候的最大子序列长度，每到一个数，开始从前面找，当当前数大于找到的数时候，对比当前的 dp[i] 和 dp[j]+1 哪个更大。

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  let dp = new Array(nums.length).fill(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[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 646. 最长数对链 (opens new window)

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例：

输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
1
2
3

题解：

方法一：动态规划

和上一题一样，本题中不是优解。思路一样，记得加上排序（用 a[0] 排 ）。

/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function (pairs) {
  pairs.sort((a, b) => a[0] - b[0])
  let dp = new Array(pairs.length).fill(1)

  for (let i = 1; i < pairs.length; i++) {
    for (let j = 0; j < i; j++) {
      if (pairs[i][0] > pairs[j][1]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二：贪心

需要记住目前最大的 a[1]，贪心是一个构筑链的过程，如果 a[0] 比 max 大才能加入链【因为比 max 大就代表比前面所有的都大(前提是 a[1] 是排序过的)】

/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function (pairs) {
  pairs.sort((a, b) => a[1] - b[1])
  let ans = 1
  let max = pairs[0][1]
  for (let i = 1; i < pairs.length; i++) {
    if (pairs[i][0] > max) {
      max = pairs[i][1]
      ans++
    }
  }
  return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 376. 摆动序列⭐ (opens new window)

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为**摆动序列。**第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。
1
2
3

示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
1
2
3

题解：

方法一：贪心

有一个 flag ，0代表上一个没有值或者是上两个之间的关系是相等的，1代表上两个的关系是上升，2代表上两个关系是下降的。当 nums[i] - nums[i - 1] > 0 且上两个的关系不是上升的时候，ans++ ，并且更新 flag ，反之亦然。

/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function (nums) {
  if (nums.length < 2) return nums.length
  // 0 null 1 up 2 down
  let flag = 0
  let ans = 1
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] - nums[i - 1] > 0 && flag != 1) {
      ans++
      flag = 1
    }
    else if (nums[i] - nums[i - 1] < 0 && flag != 2) {
      ans++
      flag = 2
    }
  }
  return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：动态规划

当前数大于前面数的时候，两种选择，一种是把down数组加上这个数变成up数组，一种是替换up数组的最后一个上升的值。反之同理

假设我们有

nums:[1,4,7,2,5]
up:[1]
down:1[1]
1
2
3
  1. 4 > 1 ①down数组加上这个数变成up数组：[1,4] ②替换up数组的最后一个上升的值 [4]。我们选择前者。
up:[1,4]
down:[4]
1
2
  1. 7 > 4 ①down数组加上这个数变成up数组：[4,7] ②替换up数组的最后一个上升的值 [1,7]。选谁都行。
up:[4,7]
down:[4]
1
2
  1. 2 < 7 ①up数组加上这个数变成down数组：[4,7,2] ②替换down数组的最后一个下降的值 [2]。我们选择前者。
up:[4,7]
down:[4,7,2]
1
2
  1. 5 > 2 ①down数组加上这个数变成up数组：[1,7,2,5] ②替换up数组的最后一个上升的值 [1,5]。我们选择前者。
up:[4,7,2,5]
down:[4,7,2]
1
2

其实变化的就是 up 和 down 的长度，我们可以用常数来做：

var wiggleMaxLength = function (nums) {
  if (nums.length < 2) return nums.length

  let up = down = 1

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] - nums[i - 1] > 0) {
      up = Math.max(up, down + 1)
    } else if (nums[i] - nums[i - 1] < 0) {
      down = Math.max(down, up + 1)
    }
  }
  return Math.max(up,down)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 字符串子序列

# 1143. 最长公共子序列⭐ (opens new window)

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

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

若这两个字符串没有公共子序列，则返回 0。

示例 1:

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

题解：

本体的思路在于 dp 的构造：

假设两个字符串为 abcde ace

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

a c e
0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3

每个格子有两种情况：

  1. text1[i - 1] === text2[j - 1]

    注意这里下标要 -1，因为对应的是数组+1 的位置。

    dp[i][j] = dp[i - 1][j - 1] + 1，相等的时候要找各自退一步那个位置的数+1，比如我分别走到 abc 和 ac ，发现 c 相等。那么就要回到 text1 的ab 位置和 text2 的 a 位置，这俩位置的 dp 值是一样的，然后 +1

  2. text1[i - 1] !== text2[j - 1]

    取上面或者左面的最大值

这题概念感觉比较抽象。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
	// 初始全是0，其实只需要 [0,0] 是0就行，后面都是根据这个来的
  let dp = Array.from({ length: text1.length + 1 }, () => 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]) {
        // 相等的时候，需要根据原来的值+1
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        // 不相等的时候可以从两个纬度走入这个格子，取最大值
        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
      }
    }
  }
  return dp[text1.length][text2.length]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 149. 单词拆分 (opens new window)

给你一个字符串 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

题解

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const set = new Set(wordDict);
  // dp[i] 代表 从0位开始长度为i的字符串是否能复合单词拆分 题目求解的就是dp[s.length]
  const dp = new Array(s.length + 1).fill(false);
  // base case 用空字符串
  dp[0] = true;

  // 以leetcode为例
  for (let i = 0; i <= s.length; i++) {
    // 假设i是2 处理的是字符串 le 目的是为了得到dp[2]的值
    // 把字符串 分别按照 ""-"le"   "l"-"e" 来判断
    for (let j = 0; j < i; j++) {
      // j为0的时候 判断 "" 和 "l"
      if (dp[j] && set.has(s.substring(j, i))) {
        // dp[j]可以拆分 且剩余的字母组成词也是存在的 则 dp[i]复合
        dp[i] = true;
        break;
      }
    }
  }

  return dp[s.length]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 0-1背包⭐

背包九讲 Link (opens new window)

# 416. 分割等和子集 (opens new window)

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

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
1
2
3
4
5

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.
1
2
3
4
5

题解：

解法一：dfs

每一步都可以选择选这个数还是跳过这个数，这个是 dfs 分叉的关键。 注意这里的 memo，用来存储已经走过的 curSum + num 的情况，可以减少很多的遍历，尤其是 [1,1,1,1,1,1....] 这种。

/**
  * @param {number[]} nums
  * @return {boolean}
    */
var canPartition = function (nums) {
  // 求和
  const sum = nums.reduce((sum, cur) => sum + cur, 0)
  // 奇偶判断
  if (sum % 2 !== 0) return false
  let target = sum / 2
  // 如果最大值比目标大，说明其他值全加起来也比目标小
  if (Math.max(...nums) > target) return false
	
  const memo = new Map()

  function dfs(curSum, i) {
    if (curSum > target || i === nums.length) return false

    if (curSum === target) return true

    const key = curSum + "+" + nums[i]
    if (memo.has(key)) {
      return memo.get(key)
    }

    const res = dfs(curSum + nums[i], i + 1) || dfs(curSum, i + 1)
    memo.set(key, res)
    return res

  }

  return dfs(0, 0)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

解法二：动态规划

dp[i][j] 代表在数[0-i]的内,背包大小为j时，这些数用一部分能不能充满背包

  • 假如我不选 nums[i]，那么我得依靠 [0-(i-1)] 这些数来填充大小为j的背包，如果他们不行那我这里也只能是 false
  • 假如我选 nums[i] ,那我把这个数先塞进去
  • 如果这个 nums[i]==j ,那么我直接true了
  • 如果 nums[i]<j ,那么剩下的空间大小是 j-nums[i] ,我可用的数字是 [0-(i-1)] ,如果这些数字能填满剩下的空间那么我就是 true，否则不行
  • 转换一下不就变成了 [0-(i-1)] 去塞 j-nums[i] 了
  • 如果 nums[i]>j ，塞都塞不下，那么只能选择不塞，不塞怎么取值上面写了
  • 另外第一行只有在正好塞满背包的情况下才可能 true
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  const sum = nums.reduce((sum, cur) => sum + cur, 0)
  if (sum % 2 !== 0) return false
  let target = sum / 2
  if (Math.max(...nums) > target) return false

  let dp = Array.from({ length: nums.length }, () => new Array(target + 1).fill(false))

  // 由于我们下面会用到dp[i - 1]，为了防止越界，我们先把第一行填了
  // 第一行只有一个值为true，也就是背包大小等于第一个值的时候，因为如果不是正好填充，那么也没有别的值能填了
  dp[0][nums[0]] = true
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j <= target; j++) {
      if (nums[i] > j) { // 塞不下，就不选了
        dp[i][j] = dp[i - 1][j]
      } else if (nums[i] === j) { // 正好相等，直接满足
        dp[i][j] = true
      } else {// 可以塞，那么我可以选择不塞或者塞
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
      }
    }
  }

  return dp[nums.length - 1][target]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 494. 目标和 (opens new window)

给定一个非负整数数组，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。
1
2
3
4
5
6
7
8
9
10
11

题解：

首先先看dp数组的定义：

dp[i][j] 定义为从数组 nums 中 0-i 的元素进行加减可以得到 j 的方法数量

图片来源 (opens new window)

image.png

  • 为什么必须要正负值到 sum ？因为我们是需要把上一行的、同列的、加上或减去 nums[i] 的两个数的 dp 值相加。在第一个数 nums[0] 的位置 0 我们需要把 1 和 -1 位置相加，同理可以一直往两边延伸到边界为 +-sum 。这里可以获得转移方程：

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

  • 如果数组只有一位或者没有的情况下，需要单独判断一下，因为我们循环行是从 1 开始。

  • 初始化第一行：在数组只有 nums[0] 的时候，背包大小只有 +-nums[0] 的时候才能各有 1 种情况，其他都是 0

  • 注意 ，如果 nums[0] == 0 的时候，+-nums[0] 是同一格，那么这一格需要初始化为 2，因为 +-0 是一样的。

/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function (nums, S) {
	// nums 长度不足以循环时
  if (nums.length < 2) {
    // 考虑正负值的情况
    if (nums[0] !== S && -nums[0] !== S) {
      return 0
    } else {
      return 1
    }
  }
	// 获得nums的总和
  const sum = nums.reduce((sum, cur) => sum + cur, 0)
  // 因为是非负整数数组，如果全部加起来还要比目标小直接返回0
  if (sum < Math.abs(S)) return 0
	// 初始化 dp
  let dp = Array.from({ length: nums.length }, () => new Array(sum * 2 + 1).fill(0))
	// 初始化第一行，考虑 0 的情况
  if (nums[0] === 0) {
    dp[0][sum] = 2
  } else {
    dp[0][sum + nums[0]] = 1
    dp[0][sum - nums[0]] = 1
  }


  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < sum * 2 + 1; j++) {
      // 判断边界情况
      const l = (j - nums[i] < 0) ? 0 : dp[i - 1][j - nums[i]]
      const r = (j + nums[i] > sum * 2) ? 0 : dp[i - 1][j + nums[i]]
			// 转移方程
      dp[i][j] = l + r
			// 如果已经到达了目标位置【最后一行的 S 值】，就可以返回了，可以少循环几次
      if (i === nums.length - 1 && j === S + sum) {
        return dp[i][j]
      }
    }
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 理解无后效性

一般的dp题目中,都会把dp[n]作为最后的答案,然后拆分问题为dp[0],dp[1]...等小问题,但是这样拆分的子问题有时候还是具有不确定的地方,这时的拆分方式就不正确,dp的子问题必须是无后效性的,也就是为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」

# 53. 最大子序和 (opens new window)

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

示例 1：

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

题解：

dp 每一位是到当前位置的最大和，也就是以当前位置为连续数组的结尾去取最大值, 不是实际的最大和, 因为如果dp的定义是到当前位置能得到的连续子数组,例如 [-2,1,-3,4],那么dp[2]是1 ,但是dp[3]就很难从前置子条件dp[2]推导,因为要依赖连续的加法,现在的dp[2]其实是数组[1],无法连续.但是如果使用 "nums[2]作为连续数组的结尾去取最大值" ,那么dp[2]对应的是数组[1,-3] => -2,这样在推导dp[3]时,由于dp[2]一定包含nums[2],dp[3]就可以用dp[2]+nums[3] => [1,-3,4]来做符合题意的连续加法,

只要上一位 dp[i-1] + 当前 num[i] 比 num[i] 大，就应该加上，如果反过来的话说明 dp[i-1] 一定是负数【因为正数加任何负数都比这个负数大】，只要是和为负数了就应该及时止损，用大的值替代。

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

对于这种每次只用到了前一位 dp[i-1] 的题目，可以考虑用常数替代

var maxSubArray = function (nums) {
  let ans = nums[0]
  let max  = nums[0]
  for (let i = 1; i < nums.length; i++) {
    max = Math.max(nums[i] + max, nums[i])
    // 每次及时更新 ans 的最大值
    ans=Math.max(ans,max)
  }
  return ans
};
1
2
3
4
5
6
7
8
9
10

# 152. 乘积最大子数组 (opens new window)

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
1
2
3

题解

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
    if (nums.length === 1) return nums[0]

    const dp = new Array(nums.length).fill({})
    dp[0] = { max: nums[0], min: nums[0] }

    for (let i = 1; i < nums.length; i++) {
        dp[i] = {
            max: Math.max(dp[i - 1].max * nums[i], dp[i - 1].min * nums[i], nums[i]),
            min: Math.min(dp[i - 1].max * nums[i], dp[i - 1].min * nums[i], nums[i])
        }
    }
    return Math.max(...dp.map(item => item.max))
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

对于dp[i]只依赖于dp[i-1]的情况,都可以用常数替代dp数组以节省空间复杂度

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  /**
   * 思路是dp, 由于dp[i]只依赖于dp[i-1],所以用常数max,min记录
   * max 和 min 表示以nums[i-1]为结尾的连续乘积的最大值和最小值
   * 之所以要记录两个值, 因为负负得正的情况下,是用前面的最小负值乘当前负值获得最大值
   * 也就是说 => dp[i]记录的是以nums[i]结尾的连续数组的最大乘积
   */
  if (nums.length === 1) return nums[0];

  let res = nums[0],
    max = nums[0],
    min = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];
    [max, min] = [
      Math.max(num, min * num, max * num),
      Math.min(num, min * num, max * num),
    ];

    res = Math.max(res, max);
  }

  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 300. 最长递增子序列 (opens new window)

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

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

示例 1：

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

题解

本题的dp定义和上面类似,是以i为结尾的子序列中,能产生的长严格递增子序列的长度,虽然子序列可以不像上面两题一样连续,但是我们的子序列结尾必须是当前的nums[i],这样一来,比如[[10,9,2,5,3,7],dp[5]就是结尾是7的子序列的最大值,当7和5比较时,5所在的dp[3]是数组[2,5]长度2,那么如果7比5大,那么和5组合的dp[5]就是2+1=3,而和3所在的dp[4]比较时,dp[5]就是1+1=2,我们从0到i位置每一个子dp和当前位置比较后的最大值即可

var lengthOfLIS = function (nums) {
  let dp = new Array(nums.length).fill(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[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)
};
1
2
3
4
5
6
7
8
9
10
11

上面这三题,都有个共同点: 为了顺利向后推导的连贯性,dp的子问题拆分都不是按照题目要的答案来拆,而是都用了当前节点作为作为当前子问题dp[i]中的最后一个元素来实现,比如53题是为了顺利让下一个元素加上前一个dp[i-1],152是为了让下一个元素顺利乘以前一个元素的最大值或者最小值,300题是为了让下一个元素顺利判断前面每一个元素的dp和当前元素是否是升序

# 其他

# 96. 不同的二叉搜索树 (opens new window)

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

示例1

png

输入：n = 3 输出：5

题解：

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
    // 核心思路,二叉搜索树的根左侧比根小 右侧比根大 左右可以为空
    /**
        dp[k] 代表k有多少种二叉搜索树,从1 到 k 开始一次做为根:
        根为1: 左边无值为0,右侧是 k-1 (这里的 k-1 就是下面解题里的 i-k,注意别绕进去)
        根为2: 左边值为1,右侧是 k-2 (只有一个数比2小 有k-2个数比2大)
        ......
        根为k-1: 左边值为k-2  右边值为1 
        根为k: 左边值为k-1  右边值为0

        dp[k]是这些情况的总和:dp[0]*dp[k-1] + dp[1]+dp[k-2]+ ... + dp[k-2]*dp[1]+dp[k-1]*dp[0]  每一种情况要用乘法
        这些用到的dp[x]里 最大的是dp[k-1] 所以我么只要从dp[0]开始一个个网上推出即可 
     */
    let dp = Array(n + 1).fill(0) // 用 0 填充n+1个 不然下面加的时候会NaN
    dp[0] = 1 // 0的时候 是空树
    dp[1] = 1

    for (i = 2; i <= n; i++) {
        // 每一个i都作为上面思路里的k 最后的dp[i]就是结果
        for (k = 1; k <= i; k++) {
            // 这个循环用来计算dp[i]  根据规律 根从1开始
            const l = k - 1
            const r = i - k
            dp[i] += dp[l] * dp[r]
        }
    }
    return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 309. 最佳买卖股票时机含冷冻期 (opens new window)

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

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

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

示例 1:

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

题解

股票通用的方法是用dp,一般确定多个状态,比如当天持股和不持股,然后找到如何从前面的状态推导出当天的状态转移公式即可,困难点在于加入的条件,比如"冷冻期""手续费",这些会限制一些推导的case

/**
 * @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]);
    }

    /** 思路1 */
    /**
    dp状态划分
    0:今天持股  - 昨天0 今天继续持股 / 昨天1 今天买入 / 昨天3 今天买入
    1:今天不持有不操作 -  昨天1 今天保持 / 昨天2 今天保持 
    2:今天不持有但操作(不加这个的话 1可能包含了昨天卖出的case 那今天就冷冻了) - 昨天0 今天卖出
    3:今天不持有但是冷冻 - 昨天2 今天保持
     */
    // let dp = Array.from(new Array(prices.length), () => new Array(4).fill(0))
    // // 第一天 0状态是买入 所以是负数 其他都是0
    // dp[0][0] = -prices[0];
    // for (i = 1; i < prices.length; i++) {
    //     dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]);
    //     dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
    //     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]);

    // ---------------------------------------------------------------------
    /** 思路2 */

    let dp = Array.from(new Array(prices.length), () => new Array(2).fill(0))
    /**
    0:持有 : 昨天持有 今天保持/ 前天卖出 今天购入(取巧的点是这个"前天卖出",今天想要持有,必须前天卖出,不考虑昨天卖出的情况了)
    1:不持有: 昨天不持有 今天保持 / 昨天持有 今天卖出
     */
    dp[0][0] = -prices[0];
    // 第一天持有:昨天就持有或者今天才持有
    // 第一次不持有:昨天不持有,或者昨天买今天卖
    dp[1][0] = Math.max(dp[0][0], -prices[1]);
    dp[1][1] = Math.max(dp[0][1], dp[0][0] + prices[1]);

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

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

← 二分查找 →