动态规划到底规划啥？

发表于

动态规划

1.1 动态规划

什么是动态规划，就是利用已知的条件，推出未知的条件

动态规划最重要的就是要找出状态转移方程，根据前面已经求出的状态，找到状态转移方程，从前面的状态转移到后面的状态

一维动态规划

70. 爬楼梯

题目描述

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

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

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

例子1

Input: 2

output: 2

解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶。

例子2

Input: 3

output: 3

解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

思考

这基本上是最经典的动态规划题目，动态规划的关键是确立动态转移方程

这里很明显可以看出dp[n] = dp[n-1]+dp[n-2],也就是爬n个台阶的方法等于爬n-1个台阶的方法和爬n-2个台阶的方法

实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
js复制代码/**
 * @param {number} n
 * @return {number}
 */
// Runtime: 72 ms, faster than 88.54% of JavaScript online submissions for Climbing Stairs.
// Memory Usage: 38.3 MB, less than 56.43% of JavaScript online submissions for Climbing Stairs.
export default (n) => {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (n === 2) return 2;
  let pre1 = 1;
  let pre2 = 2;
  for (let i = 3; i <= n; i++) {
    const temp = pre2;
    pre2 = pre1 + pre2;
    pre1 = temp;
  }
  return pre2;
};

时间复杂度O（n）， 空间复杂度O（1）

198. 打家劫舍

题目描述

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

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

例子1

Input: [1,2,3,1]

output: 4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

例子2

Input: [2,7,9,3,1]

output: 12

解释： 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12

提示：

1 0 <= nums.length <= 100

2 0 <= nums[i] <= 400

思考

这基本上是最经典的动态规划题目，动态规划的关键是确立动态转移方程

动态规划一般是利用已知的前面保存的状态推出下面的状态

假设dp[n]是数组长度为n的房屋可以盗窃的最大金额，那么现在可以思考下当dp[n+1]的时候，可以盗窃的最大金额是什么呢？

可以很容易的想到dp[n+1]要么不盗窃n+1的房屋的金额，那么肯定是等于dp[n],要么盗窃n+1房屋的金额，那么当盗窃n+1房屋金额的时候，总盗窃金额是dp[n+1] = dp[n-2]+(n+1)房屋的金额

实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */
// Runtime: 68 ms, faster than 97.89% of JavaScript online submissions for House Robber.
// Memory Usage: 38.2 MB, less than 91.14% of JavaScript online submissions for House Robber.
export default (nums) => {
  if (!nums) return 0;
  if (nums.length === 1) return nums[0];
  if (nums.length === 2) return Math.max(nums[0], nums[1]);

  let preN2money = nums[0];
  let preN1money = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    const temp = preN1money;
    preN1money = Math.max(preN1money, preN2money + nums[i]);
    preN2money = temp;
  }
  return preN1money;
};

时间复杂度O（n）， 空间复杂度O（1）

198. 打家劫舍II

题目描述

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

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

例子1

Input: nums = [2,3,2]

output: 3

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

例子2

Input: nums = [1,2,3,1]

output: 4

解释： 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

例子3

Input: nums = [0]

output: 0

提示：

1 0 <= nums.length <= 100

2 0 <= nums[i] <= 1000

思考

这里基本上延续上面的打家劫舍的题目，但是和上面不一样的是这里是一个循环，从末尾又连到了开始，所以这里该如何解决呢？

如果想要解决一个问题，首先就要明白问题是什么？如果把问题定义的很清楚，也就离解决问题不远了

那这里和打家劫舍有哪些不同呢？

如果想不到，可以写个测试用例，自己看看，比如房屋的金额分别是[2,3,2],我们会得到什么结果呢？

走到这里，相信基本上已经明白了问题在哪了，我们如果按照打家劫舍的解法去做，可以发现因为我们不确定从第一家还是第二家开始打劫，所以如果我们从第一家开始打劫的话，打劫到最后一家的时候，因为最后一家和第一家相连，所以就触发了报警

所以问题也就清楚了，我们如何确定当打劫到到最后一家的时候，如何确定我们没有打劫第一家呢？

应该很容易想到我们如果从第二家开始打劫，一直到最后一家，肯定不会触发报警。

但是从第二家开始是不是就是结果呢？

我们能不能也从第一家开始打劫呢?如果从第一家开始打劫，我们是不是打劫到倒数第二家就可以了？

可以发现这两种情况的最大的，就是我们可以打劫到的最大金额。

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */
// Runtime: 68 ms, faster than 98.02% of JavaScript online submissions for House Robber II.
// Memory Usage: 38.5 MB, less than 53.03% of JavaScript online submissions for House Robber II.
export default (nums) => {
  if (!nums) return 0;
  if (nums.length === 1) return nums[0];
  if (nums.length === 2) return Math.max(nums[0], nums[1]);
  let preN2money = nums[0];
  let preN1money = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length - 1; i++) {
    const temp = preN1money;
    preN1money = Math.max(preN1money, preN2money + nums[i]);
    preN2money = temp;
  }
  let preN2money2 = nums[1];
  let preN1money1 = Math.max(nums[1], nums[2]);
  for (let i = 3; i < nums.length; i++) {
    const temp = preN1money1;
    preN1money1 = Math.max(preN1money1, preN2money2 + nums[i]);
    preN2money2 = temp;
  }
  return Math.max(preN1money1, preN1money);
};

时间复杂度O（n）， 空间复杂度O（1）

343. 整数拆分

题目描述

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

例子1

Input: 2

output: 1

解释：2 = 1 + 1, 1 × 1 = 1。

例子2

Input: 10

output: 36

解释：10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

思考

1 题目本身的状态转移方程一眼就可以看出来
dp[i] = Math.max(dp[i], dp[i-j] * d[j])

但是这里隐藏着一个坑，如果想不到，思路是对的，但是测试用例应该还是过不了的？

因为这里dp[j]可能比j小，dp[i-j]也可能比i-j小

比如dp[4]本来最大的值应该是2 * 2 ,但是
dp[2] * dp [2] =1， dp[3] * dp [1] = 3

很明显不对

实现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
js复制代码/**
 * @param {number} n
 * @return {number}
 */
// Input: 2
// Output: 1
// Explanation: 2 = 1 + 1, 1 × 1 = 1.

// Input: 10
// Output: 36
// Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
// Runtime: 72 ms, faster than 98.97% of JavaScript online submissions for Integer Break.
// Memory Usage: 38.3 MB, less than 82.47% of JavaScript online submissions for Integer Break.
export default (n) => {
  if (n <= 1) return 0;
  if (n === 2) return 1;
  const dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    for (let j = 1; 2 * j <= i; j++) {
      const maxJ = Math.max(j, dp[j]);
      const maxDis = Math.max(i - j, dp[i - j]);
      dp[i] = Math.max(dp[i], maxJ * maxDis);
    }
  }
  // console.log(dp);
  return dp[n];
};

时间复杂度O（n * lgn）， 空间复杂度O（n）

650. 只有两个键的键盘

题目描述

最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：

1 Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。

2 Paste (粘贴) : 你可以粘贴你上一次复制的字符。

给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。

例子1

Input: 3

output: 3

解释：
最初, 我们只有一个字符 ‘A’。

第 1 步, 我们使用 Copy All 操作。

第 2 步, 我们使用 Paste 操作来获得 ‘AA’。

第 3 步, 我们使用 Paste 操作来获得 ‘AAA’。

说明：
1 n 的取值范围是 [1, 1000] 。

思考

1 题目比较简单，就是单纯的dp

我刚开始实现的时候，只是考虑了偶数的情况，没有考虑到奇数也可以被整除的

比如当n=9的时候，9也是可以整除到3的。

参考实现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
js复制代码/**
 * @param {number} n
 * @return {number}
 */
// Runtime: 88 ms, faster than 53.27% of JavaScript online submissions for 2 Keys Keyboard.
// Memory Usage: 39.3 MB, less than 31.78% of JavaScript online submissions for 2 Keys Keyboard.
export default (n) => {
  const dp = new Array(n + 1).fill(Number.MAX_VALUE);
  dp[0] = 0;
  dp[1] = 0;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    if (i % 2 === 0) {
      dp[i] = Math.min(dp[i], dp[i / 2] + 2, i);
    } else {
      dp[i] = Math.min(dp[i], i);
      for (let k = 3; k < Math.floor(i / 2); k++) {
        if (i % k === 0) {
          dp[i] = Math.min(dp[i], dp[k] + i / k);
        }
      }
    }
  }
  return dp[n];
};

时间复杂度O（n ^ 2）， 空间复杂度O（1）

376. 摆动序列

题目描述

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

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

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

例子1

Input: [1,7,4,9,2,5]

output: 6

解释：整个序列均为摆动序列。

例子2

Input: [1,17,5,10,13,15,10,5,16,8]

output: 7

解释：这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

例子3

Input: [1,2,3,4,5,6,7,8,9]

output: 2

解释：比如[1,2]就是一个摆动序列

思考

1 如果是单纯的增长或者减少使用动态规划比较简单，但是这里是一个摆动序列，可能就比较麻烦了

这种涉及到几种状态的，可以拆开

这里就是拆开两种状态，分别动态规划

参考实现1

压缩空间的参考实现2

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */

// Runtime: 76 ms, faster than 72.34% of JavaScript online submissions for Wiggle Subsequence.
// Memory Usage: 38.5 MB, less than 44.68% of JavaScript online submissions for Wiggle Subsequence.
export default (nums) => {
  if (nums.length === 0 || !nums) return 0;
  if (nums.length <= 1) return 1;
  if (nums.length === 2) {
    return nums[0] !== nums[1] ? 2 : 1;
  }
  const len = nums.length;
  const up = new Array(len).fill(0);
  const down = new Array(len).fill(0);

  up[0] = 1;
  down[0] = 1;

  for (let i = 1; i < len; i++) {
    if (nums[i] > nums[i - 1]) {
      up[i] = down[i - 1] + 1;
      down[i] = down[i - 1];
    } else if (nums[i] < nums[i - 1]) {
      down[i] = up[i - 1] + 1;
      up[i] = up[i - 1];
    } else {
      down[i] = down[i - 1];
      up[i] = up[i - 1];
    }
  }

  return Math.max(down[nums.length - 1], up[nums.length - 1]);
};

时间复杂度O（n）， 空间复杂度O（n）

实现2

1
2
3
4
5
6
7
8
9
10
11
12
js复制代码// Runtime: 76 ms, faster than 72.34% of JavaScript online submissions for Wiggle Subsequence.
// Memory Usage: 38.5 MB, less than 36.17% of JavaScript online submissions for Wiggle Subsequence.
export default (nums) => => {
  if (nums.length < 2) return nums.length;
  let down = 1;
  let up = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) up = down + 1;
    else if (nums[i] < nums[i - 1]) down = up + 1;
  }
  return Math.max(down, up);
};

时间复杂度O（n）， 空间复杂度O（1）

413. 等差数列划分

题目描述

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

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

1, 3, 5, 7, 9

7, 7, 7, 7

3, -1, -5, -9

数组 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 中所有为等差数组的子数组个数。

例子1

Input: A = [1, 2, 3, 4]

output: 3

解释：A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

思考

1 第一种dp[n]表示n结尾的一共有多少种排列，所以dp[n+1]呢？

这里应该很容易想到dp[n+1] 等于dp[n]和以n+1结尾的数字可以组成的等差数列的和。

不过这里需要注意的是虽然给出的测试用例是排好序的，但是实际上并没有排好序，所以不要按照排好序来处理

可以看下实现1

2 这里如果换一种看法，如果让dp[n]还是表示以下标为n结尾一共有多少种排列？

那么dp[n+1]有多少种呢？

如果想不到，可以试试测试用例[1,2,3,4,5]

分别写下dp[1],dp[2]..dp[5]的结果，看下有什么规律

所以很容易看到dp[n+1] = dp[n]+1,最后因为我们统一的是每个位置的排列数，所以最后求和就可以了

可以看下实现2，明显可以看出实现2比实现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
js复制代码/**
 * @param {number[]} A
 * @return {number}
 */
// Runtime: 84 ms, faster than 18.63% of JavaScript online submissions for Arithmetic Slices.
// Memory Usage: 41.1 MB, less than 5.88% of JavaScript online submissions for Arithmetic Slices.
export default (A) => {
  if (!A || A.length < 3) return [];
  let dp = [];
  if (A[2] - A[1] === A[1] - A[0]) {
    dp.push([A[0], A[1], A[2]]);
  }
  for (let i = 3; i < A.length; i++) {
    const tempArr = [];
    tempArr.push(A[i]);
    const val = A[i] - A[i - 1];
    for (let k = i - 1; k >= 0; k--) {
      if (tempArr[0] - A[k] === val) {
        tempArr.unshift(A[k]);
        if (tempArr.length >= 3) {
          dp.push([...tempArr]);
        }
      } else {
        break;
      }
    }
  }
  return dp.length;
};

时间复杂度O（n^2）， 空间复杂度O（n^2）

实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
js复制代码// Runtime: 76 ms, faster than 76.47% of JavaScript online submissions for Arithmetic Slices.
// Memory Usage: 38.4 MB, less than 51.96% of JavaScript online submissions for Arithmetic Slices.
export default (A) => {
  if (!A || A.length < 3) return [];
  const len = A.length;
  const dp = new Array(len).fill(0);
  for (let i = 2; i < len; ++i) {
    if (A[i] - A[i - 1] === A[i - 1] - A[i - 2]) {
      dp[i] = dp[i - 1] + 1;
    }
  }
  // console.log(dp);
  return dp.reduce((a, b) => a + b);
};

时间复杂度O（n）空间复杂度O（n）

53. 最大子序和

题目描述

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

进阶：

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

例子1

Input: [-2,1,-3,4,-1,2,1,-5,4]

output: 6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

例子2

Input: [1]

output: 1

例子3

Input: [0]

output: 0

例子4

Input: [-1]

output: -1

例子5

Input: [-2147483647]

output: -2147483647

提示：

1 1 <= nums.length <= 2 * 10^4

2 -2^31 <= nums[i] <= 2^31 - 1

思考

1 第一种dp[n]表示n结尾的一共有多少种排列，所以dp[n+1]呢？

这里应该很容易想到dp[n+1] 等于dp[n]和以n+1结尾的数字可以组成的等差数列的和。

不过这里需要注意的是虽然给出的测试用例是排好序的，但是实际上并没有排好序，所以不要按照排好序来处理

可以看下实现1

2 这里如果换一种看法，如果让dp[n]还是表示以下标为n结尾一共有多少种排列？

那么dp[n+1]有多少种呢？

如果想不到，可以试试测试用例[1,2,3,4,5]

分别写下dp[1],dp[2]..dp[5]的结果，看下有什么规律

所以很容易看到dp[n+1] = dp[n]+1,最后因为我们统一的是每个位置的排列数，所以最后求和就可以了

可以看下实现2，明显可以看出实现2比实现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
js复制代码/**
 * @param {number[]} A
 * @return {number}
 */
// Runtime: 84 ms, faster than 18.63% of JavaScript online submissions for Arithmetic Slices.
// Memory Usage: 41.1 MB, less than 5.88% of JavaScript online submissions for Arithmetic Slices.
export default (A) => {
  if (!A || A.length < 3) return [];
  let dp = [];
  if (A[2] - A[1] === A[1] - A[0]) {
    dp.push([A[0], A[1], A[2]]);
  }
  for (let i = 3; i < A.length; i++) {
    const tempArr = [];
    tempArr.push(A[i]);
    const val = A[i] - A[i - 1];
    for (let k = i - 1; k >= 0; k--) {
      if (tempArr[0] - A[k] === val) {
        tempArr.unshift(A[k]);
        if (tempArr.length >= 3) {
          dp.push([...tempArr]);
        }
      } else {
        break;
      }
    }
  }
  return dp.length;
};

时间复杂度O（n^2）， 空间复杂度O（n^2）

实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
js复制代码// Runtime: 76 ms, faster than 76.47% of JavaScript online submissions for Arithmetic Slices.
// Memory Usage: 38.4 MB, less than 51.96% of JavaScript online submissions for Arithmetic Slices.
export default (A) => {
  if (!A || A.length < 3) return [];
  const len = A.length;
  const dp = new Array(len).fill(0);
  for (let i = 2; i < len; ++i) {
    if (A[i] - A[i - 1] === A[i - 1] - A[i - 2]) {
      dp[i] = dp[i - 1] + 1;
    }
  }
  // console.log(dp);
  return dp.reduce((a, b) => a + b);
};

时间复杂度O（n）空间复杂度O（n）

279. 完全平方数

题目描述

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

例子1

Input: n = 12

output: 3

解释：12 = 4 + 4 + 4.

例子2

Input: n = 13

output: 2

解释：13 = 4 + 9.

思考

1 动态规划最重要的是什么？

一般主要是找到状态转移方程，这里的状态转移其实也很简单

这里我是怎么想出来的呢？

观察测试用例

// Input: n = 12

// output: 3

// 解释：12 = 4 + 4 + 4.

//

// 例子2

// Input: n = 13

// output: 2

// 解释：13 = 4 + 9.

可以看到dp[13]是dp[4] + 3 * 3,dp[12] 是dp[8] + 2 * 2,而dp[8] = dp[4] + 2 * 2

所以这里的状态转移方程就是dp[n] = Math.min(dp[n-i]+1),并且n = n- i* i + 1

可以参考下实现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
js复制代码/**
 * @param {number} n
 * @return {number}
 */

// Input:  n = 12<br/>
// output: 3<br/>

// 解释：12 = 4 + 4 + 4.
// <br/>

// 例子2<br/>
// Input:  n = 13 <br/>
// output: 2<br/>
// 解释：13 = 4 + 9.

// dp[13] = dp[]

// dp[1] = 1
// dp[2] = 1+1
// dp[n] = dp[n-]
export default (n) => {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (n === 2) return 2;
  const dp = [];
  dp[0] = 0;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = Number.MAX_VALUE;
    const sqrtN = Math.floor(Math.sqrt(i));
    for (let j = 1; j <= sqrtN; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
};

时间复杂度O（1到n的根号的和）， 空间复杂度O（n）

646. 最长数对链

题目描述

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

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

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

例子1

Input: [[1,2], [2,3], [3,4]]

output: 2

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

提示：

给出数对的个数在 [1, 1000] 范围内。

思考

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
js复制代码/**
 * @param {number[][]} pairs
 * @return {number}
 */
//  Runtime: 92 ms, faster than 92.21% of JavaScript online submissions for Maximum Length of Pair Chain.
//  Memory Usage: 42.8 MB, less than 74.03% of JavaScript online submissions for Maximum Length of Pair Chain.
export default (pairs) => {
  if (!pairs || pairs.length === 0) return [];

  if (pairs.length === 1 || pairs.length === 2) return [pairs[0]];
  pairs.sort((a, b) => a[0] - b[0]);
  const dp = [pairs[0]];
  // console.log(pairs);
  for (let i = 1; i < pairs.length; i++) {
    if (pairs[i][0] > dp[dp.length - 1][1]) {
      dp.push(pairs[i]);
    } else if (pairs[i][1] < dp[dp.length - 1][1]) {
      dp[dp.length - 1] = pairs[i];
    }
  }
  // console.log(dp);
  return dp.length;
};

时间复杂度O（n）， 空间复杂度O（n）

91. 解码方法

题目描述

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

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

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

例子1

Input: s = “12”

output: 2

解释：它可以解码为 “AB”（1 2）或者 “L”（12）

例子2

Input: s = “226”

output: 3

解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

例子3

Input: s = “0”

output: 0

例子4

Input: s = “1”

output: 1

例子5

Input: s = “2”

output: 1

思考

1 刚开始思考，通过”226” 这个测试用例，很容易的可以得出状态转移方程是dp[n] = dp[n-1] + dp[n-2] 或者dp[n] = dp[n-1]

本题的难度不在于状态转移方程的思考，而是在于各种不同情况的处理

比如这里你可以思考下以下测试用例如何处理

“12” => 2

“226” => 3

“00” => 0

“2101” => 1

“27” => 1

“1201234” => 3

“10011” => 0

“123123” => 9

“230” => 0

正常的思考路程肯定是处理各种情况，可以参考实现1

2 通过上面的情况，可以发现各种情况需要各种处理，代码虽然不是很复杂，但是需要处理的各种情况，都需要处理，代码显得冗余，而且不优雅，显得代码难看

可以把上面的各种情况进行统一处理下

这里我们需要思考下为什么上面的情况那么复杂，需要处理的情况为什么那么多？

可以发现就是“0”的各种情况，所以需要各种特殊处理

这里有两种情况

如果当前的数字不是0，那没什么说的，最基本的是dp[i] += dp[i-1]

然后就是要处理要不要再加上dp[i-2],换句话说就是最后两个数字是不是在1到26之间，如果在1到26之间，就需要加上dp[i-2],如果不在，则不需要

可以参考实现2，可以看到代码简洁了很多

实现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
js复制代码/**
 * @param {string} s
 * @return {number}
 */
// dp[3] = dp[1]+dp[2]
// Runtime: 104 ms, faster than 22.88% of JavaScript online submissions for Decode Ways.
// Memory Usage: 42.5 MB, less than 15.00% of JavaScript online submissions for Decode Ways.
export default (s) => {
  if (s.length === 1 && +s > 0) {
    return 1;
  } else if (s.length === 1 || s[0] === "0") {
    return 0;
  }
  const dp = [];
  dp[0] = +s[0] > 0 ? 1 : 0;
  dp[1] = +s[1] > 0 ? dp[0] + 1 : dp[0];

  if (+s.substring(0, 2) > 26 && +s[0] > 0 && s[1] !== "0") {
    dp[1] = 1;
  } else if (+s.substring(0, 2) > 26 && +s[0] > 0 && s[1] === "0") {
    return 0;
  }

  for (let i = 2; i < s.length; i++) {
    if (s[i] === "0" && +s.substring(i - 1, i + 1) < 27 && +s.substring(i - 1, i + 1) > 9) {
      dp[i] = dp[i - 2];
    } else if (+s[i - 1] > 0 && +s[i] > 0 && +s.substring(i - 1, i + 1) > 10 && +s.substring(i - 1, i + 1) < 27) {
      dp[i] = dp[i - 1] + dp[i - 2];
    } else if ((+s[i - 1] === 0 && +s[i] > 0) || (+s[i - 1] > 0 && +s[i] > 0 && +s.substring(i - 1, i + 1) > 26)) {
      dp[i] = dp[i - 1];
    } else if ((+s[i] === 0 && +s.substring(i - 1, i + 1) > 26) || (+s[i - 1] === 0 && +s[i] === 0)) {
      return 0;
    }
  }
  // console.log(dp);
  return dp[dp.length - 1];
};

时间复杂度O（n）， 空间复杂度O（n）

实现2

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
js复制代码/**
 * @param {string} s
 * @return {number}
 */
export default (s) => {
  if (s.length === 0) return 0;

  const len = s.length;
  const dp = new Array(len + 1).fill(0);

  dp[0] = 1;
  // 当有一个字符的时候
  dp[1] = s[0] === "0" ? 0 : 1;

  for (let i = 2; i <= len; i++) {
    // 如果不等于0，肯定是等于dp[n-1]
    if (s[i - 1] !== "0") {
      dp[i] += dp[i - 1];
    }
    // console.log(dp[i], i);
    // 如果等于0或者小于6的情况下加上dp[n-2]
    if (s[i - 2] === "1" || (s[i - 2] === "2" && s[i - 1] <= "6")) {
      dp[i] += dp[i - 2];
    }
    // console.log(dp[i], i);
  }
  // console.log(dp);
  return dp[len];
};

时间复杂度O(n), 空间复杂度O(n)

139. 单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

1 拆分时可以重复使用字典中的单词。

2 你可以假设字典中没有重复的单词。

例子1

Input: s = “leetcode”, wordDict = [“leet”, “code”]

output: true

解释：返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

例子2

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]

output: true

解释：返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

例子3

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]

output: false

思考

1 这里使用动态规划比较简单，很容易就可以想到dp[n]表示长度为n的字符串是否可以用wordDict表示，那么dp[n+1]呢？

这里应该比较简单,可以想下dp[n+1]什么时候为true，什么时候为false呢？

那肯定是如果发从s[n+1]到s[i]的字符串可以用wordDict表示，同时dp[i-1]也可以表示的时候，那么dp[n+1]肯定是true了。

实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
js复制代码/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */

// Runtime: 88 ms, faster than 57.62% of JavaScript online submissions for Word Break.
// Memory Usage: 40.5 MB, less than 62.66% of JavaScript online submissions for Word Break.
export default (s, wordDict) => {
  // dp[i] 表示s中前i个字符是否可以在wordDict中表示
  const dp = new Array(s.length).fill(0);

  for (let i = 0; i < s.length; i++) {
    for (let j = i; j >= 0; j--) {
      const subStr = s.substring(j, i + 1);
      if (wordDict.includes(subStr) && ((dp[j - 1] === 1 && j > 0) || j === 0)) {
        dp[i] = 1;
      }
    }
  }
  return dp[s.length - 1];
};

时间复杂度O（n * n * wordDict.length），

空间复杂度O（n）

300. 最长上升子序列

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

例子1

Input:

[10,9,2,5,3,7,101,18]

output: 4

解释： 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

例子2

Input:

nums = [0,1,0,3,2,3]

output: 4

例子3

Input:

nums = [7,7,7,7,7,7,7]

output: 1

提示：

1 1 <= nums.length <= 2500

2 -10^4 <= nums[i] <= 10^4<br

思考

1 题目使用动态规划，dp[i]表示以nums[i]结尾的增长子数列

然后很容易就可以发现状态转移方程dp[i] 等于 i 前面所有小于nums[i]的子数列的最大值

代码比较简单，参考实现1

2 然后题目还要求实现O（n * lgn）的时间复杂度，涉及到lgn肯定是二分查找，可以在哪里查找呢？

在原数组中查找肯定不可能，那在哪里查找呢？可以发现在上面实现1中为什么是O(n * n)? 有哪些可以改进呢？

可以发现上面就是因为需要不断去遍历前面的结果，那么我们是否可以改进下，重新定义dp[i]的含义，让dp[i]表示包含i+1个数字的增长数列。

那么dp就是一个nums中增长子数列，现在已经知道dp[i],那么如何更新dp呢？

现在有新的nums[i+1]了，那么如何更新dp呢？

可以发现在dp中使用二分查找找到nums[i+1]的位置，根据什么查找位置呢？

就是nums[i+1]在dp中的位置pos，等于nums[i+1]>dp[pos] && nums[i+1]<dp[pos+1]，或者直接替换dp[dp.length-1]

num dp

10 [10] 10加入dp

9 [9] 9加入的时候，发现9比10小，为了更长子数列，9替换10

2 [2] 2加入的时候，发现2比9小，为了更长子数列，2替换 9

5 [2，5] 5 加入，发现比大，变为 [2，5]

3 [2,3] 3比5小

7 [2,3,7] 7 比 3大

101 [2,3,7,101] 101比7大

18 [2,3,7,18] 18比101小

可以参考实现2

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */
//  [10,9,2,5,3,7,101,18]
//  4
// Runtime: 184 ms, faster than 18.89% of JavaScript online submissions for Longest Increasing Subsequence.
// Memory Usage: 39.6 MB, less than 25.03% of JavaScript online submissions for Longest Increasing Subsequence.
export default (nums) => {
  const len = nums.length;
  const dp = new Array(len).fill(1);
  let max = 1;
  for (let i = 1; i < nums.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[j] + 1, dp[i]);
        max = Math.max(dp[i], max);
      } else if (nums[i] === nums[j]) {
        dp[i] = Math.max(dp[i], dp[j]);
        max = Math.max(dp[i], max);
      }
    }
  }
  return max;
};

时间复杂度O（n * n), 空间复杂度O（ n）

实现2

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
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */
//  [10,9,2,5,3,7,101,18]
//  4

const binarySearchPosition = (dp, target, high) => {
  let low = 0;
  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (target === dp[mid]) return mid;
    else if (target < dp[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return low;
};
// [10, 9, 2, 5, 3, 7, 101, 18];
// Runtime: 84 ms, faster than 90.03% of JavaScript online submissions for Longest Increasing Subsequence.
// Memory Usage: 40.2 MB, less than 19.47% of JavaScript online submissions for Longest Increasing Subsequence.
export default (nums) => {
  const len = nums.length;
  if (!nums || len === 0) return 0;
  if (len === 1) return 1;
  let dp = new Array(len).fill(Number.MAX_VALUE);
  for (let i = 0; i < len; i++) {
    let pos = binarySearchPosition(dp, nums[i], i);
    dp[pos] = nums[i];
    console.log(dp);
  }

  for (let i = dp.length - 1; i >= 0; i--) {
    if (dp[i] !== Number.MAX_VALUE) return i + 1;
  }

  return 0;
};

时间复杂度O（n * lgn），空间复杂度O(n)

二维动态规划

1143. 最长公共子序列

题目描述

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

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

例子1

Input: text1 = “abcde”, text2 = “ace”

output: 3

解释：最长公共子序列是 “ace”，它的长度为 3。

例子2

Input: text1 = “abc”, text2 = “abc”

output: 3

解释：最长公共子序列是 “abc”，它的长度为 3。

例子3

Input: text1 = “abc”, text2 = “def”

output: 0

解释：两个字符串没有公共子序列，返回 0。

提示：

1 1 <= text1.length <= 1000

2 1 <= text2.length <= 1000

3 输入的字符串只含有小写英文字符。

思考

1 这里是求公共子序列，动态规划中一般dp[i]是指i结尾的子序列

因为这里涉及到两个字符串，很容易想到使用二维动态规划
dp[i][j]

dp[i][j] 可以用来表示第一个字符串中i结尾和第二个字符串j结尾的包含的公共子序列

那么状态转移方程是什么呢？

可以看下测试用例text1 = “abcde”, text2 = “ace”

可以看到dp[1][1] = 1，因为”a”等于“a”，那么接下来问题就来了？

dp[i+1][j] 是什么？

dp[i][j+1]是什么？

dp[i][j]是什么？

可以看到dp[2][1]=1,dp[1][2] =1 ,dp[2][2] = 1

那么有什么关系呢？

可以看到如果dp[i+1]等于dp[j+1],那么 dp[i+1][j+1]=dp[i][j]+1,如果dp[i+1]不等于dp[j+1]，那么dp[i+1][j+1]要么等于dp[i+1][j]要么等于dp[i][j+1]，也就是dp[i+1][j+1]=Math.max(dp[i+1][j],dp[i][j+1])

有了状态转移方程，代码就很容易了

参考实现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
js复制代码/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */

//  Runtime: 116 ms, faster than 62.14% of JavaScript online submissions for Longest Common Subsequence.
//  Memory Usage: 48.4 MB, less than 91.40% of JavaScript online submissions for Longest Common Subsequence.
// export default (text1, text2) => {
  const m = text1.length;
  const n = text2.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }
  // console.log(dp);
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++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]);
      }
    }
  }
  // console.log(dp);
  return dp[m][n];
};

时间复杂度O（m * n), 空间复杂度O（m * n）

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

题目描述

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

例子1

Input: “sea”, “eat”

output: 2

解释：第一步将”sea”变为”ea”，第二步将”eat”变为”ea”

提示：

1 给定单词的长度不超过500。

2 给定单词中的字符只含有小写字母。

思考

1 这里是上面的1143的变种题目，可以想下两者有那些不同?
做题不是目的，举一反三才是本质

那么两者有哪些不一样呢？

我们可以从1143得到那些提示，如何修改才能解决本题呢？

从上面的1143可以得出我们同样可以定义dp[i][j],但是这里的状态转移方程是什么呢？

很容易想到，如果word1[i]等于word[j],那么dp[i][j] 就等于dp[i-1][j-1]

这里比较困难的是如何处理word1[i]不等于word[j]的时候，如何处理呢？

可以想下

这里可以提供一个思路，一般二维动态规划的状态转移方程，dp[i][j] 一般和dp[i-1][j],dp[i][j-1],
dp[i-1][j-1] 有关

然后应该可以得出
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;

参考实现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
js复制代码/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

// "sea", "eat";

// Runtime: 108 ms, faster than 93.48% of JavaScript online submissions for Delete Operation for Two Strings.
// Memory Usage: 45 MB, less than 75.00% of JavaScript online submissions for Delete Operation for Two Strings.
export default (word1, word2) => {
  if (word1 === word2) {
    return 0;
  }
  if (word1.length === 0) {
    return word2.length;
  }
  if (word2.length === 0) {
    return word1.length;
  }
  const m = word1.length;
  const n = word2.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }
  for (let i = 1; i <= n; i++) {
    dp[0][i] = i;
  }
  for (let i = 1; i <= m; i++) {
    dp[i][0] = i;
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; 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], dp[i][j - 1]) + 1;
      }
    }
  }
  // console.log(dp);
  return dp[m][n];
};

时间复杂度O（m * n), 空间复杂度O（m * n）

64. 最小路径和

题目描述

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

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

例子1

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

output: 7

解释：因为路径 1→3→1→1→1 的总和最小。

例子2

Input: grid = [[1,2,3],[4,5,6]]

output: 12

提示：

1 m == grid.length

2 n == grid[i].length<br
3 1 <= m, n <= 200

4 0 <= grid[i][j] <= 100

思考

1 题目比较简单，状态转移方程很容易就可以看出来

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

参考实现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
js复制代码/**
 * @param {number[][]} grid
 * @return {number}
 */
// Runtime: 84 ms, faster than 68.34% of JavaScript online submissions for Minimum Path Sum.
// Memory Usage: 41.1 MB, less than 30.49% of JavaScript online submissions for Minimum Path Sum.
export default (grid) => {
  const m = grid.length;
  const n = grid[0].length;
  if (m === 1 && n === 1) {
    return grid[0][0];
  }
  const dp = [];
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(0);
  }
  dp[0][0] = grid[0][0];
  for (let i = 1; i < n; i++) {
    dp[0][i] = dp[0][i - 1] + grid[0][i];
  }
  for (let i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0];
  }

  // dp[0];
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
  return dp[m - 1][n - 1];
};

时间复杂度O（m * n), 空间复杂度O（m * n）

542. 01 矩阵

题目描述

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

例子1

Input:

[[0,0,0],
[0,1,0],
[0,0,0]]

output:
[[0,0,0],
[0,1,0],
[0,0,0]]

例子2

Input:

[[0,0,0],
[0,1,0],
[1,1,1]]

output:
[[0,0,0],
[0,1,0],
[1,2,1]]

提示：

1 给定矩阵的元素个数不超过 10000。

2 给定矩阵中至少有一个元素是 0。<br
3 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

思考

1 状态转移方程很好找，如果matrix[i][j]等于1，则dp[i][j]是四个方向中最小的值加1

但是很明显这样不对，因为就会形成循环了

那么如果避免死循环呢

后来想到了可以先从上到下遍历一遍，然后再从下到上遍历一遍，可是发现这样有个情况不是很好处理，那就是不管从上到下，还是从下到上，到matrix[0][0]等于0的时候，如何设置dp[0][0]?

可以想想应该如何设置？

后来才发现，因为是需要找到最小的，我们刚开是就直接设置dp的每个值是MAX_VALUE就可以了，如果从上到下，肯定能找到最小的

当时陷入了一个怪区，总是希望先设置完dp[0][0],才能从上到下遍历

参考实现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
js复制代码/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
// Runtime: 148 ms, faster than 96.10% of JavaScript online submissions for 01 Matrix.
// Memory Usage: 46.8 MB, less than 79.22% of JavaScript online submissions for 01 Matrix.
export default (matrix) => {
  const m = matrix.length;
  const n = matrix[0].length;
  if (m === 0) {
    return [[]];
  }
  const dp = [];
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(Number.MAX_VALUE);
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === 0) {
        dp[i][j] = 0;
      } else {
        if (i > 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
        }
        if (j > 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
        }
      }
    }
  }
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      if (matrix[i][j] != 0) {
        if (i < m - 1) {
          dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
        }
        if (j < n - 1) {
          dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
        }
      }
    }
  }
  return dp;
};

时间复杂度O（m * n), 空间复杂度O（m * n）

221. 最大正方形

题目描述

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

例子1

38121a5f0e1ab3a7c6a38bc5aff97e91.jpeg

Input:

matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]

output: 4

例子2

7a1e23b526e764e795e12ef50d9bea3f.jpeg

Input:

matrix = [[“0”,”1”],[“1”,”0”]]

output: 1

例子3

Input:

matrix = matrix = [[“0”]]

output: 0

提示：

1 m == matrix.length

2 n == matrix[i].length<br
3 1 <= m, n <= 300

4 matrix[i][j] 为 ‘0’ 或 ‘1’

思考

1 题目使用动态规划，这里一看就是使用二维动态规划

dp[i][j]表示以matrix[i][j]为结尾的1的最大正方形

那么状态转移方程呢？

这里状态转移方程从逻辑上很容易发现，但是在代码中很难实现

刚开始我想求dp[i][j]的值，分别以
dp[i-1][j-1],dp[i][j-1],dp[i-1][j]分别计算出包含matrix[i][j]的最大正方形，可是发现代码写起来特别乱，及时一些测试用例可以过，但是很多测试过不了

这里的难点就是如何确立简单的状态转移方程？

不过这里确实不好想到，最多可能就是使用测试用例，一个个总结规律

假设dp[i][j]的最大正方形是k^2,那么充分条件为 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 的值必须 都不小于 (k − 1)^2，否则 (i, j) 位置不可以构成一个边长为 k 的正方形。

所以如果dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j]三个值中的最大正方形的边长最小值为 k − 1，也就是三者的最大正方形都不小于(k − 1)^2，则
dp[i][j] 位置一定且最大可以构成一个边长为 k 的正方形，因为dp[i][j]的最大正方形是k^2

51dc1ef58e498a3a99383fcc0b07d10f.png

代码比较简单，参考实现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
js复制代码/**
 * @param {character[][]} matrix
 * @return {number}
 */

// Runtime: 84 ms, faster than 94.48% of JavaScript online submissions for Maximal Square.
// Memory Usage: 42.2 MB, less than 29.75% of JavaScript online submissions for Maximal Square.

export default (matrix) => {
  const m = matrix.length;
  const n = matrix[0].length;
  if (m === 0 || n === 0) {
    return 0;
  }
  const dp = [];
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(0);
  }

  let max = 0;
  for (let i = 0; i < n; i++) {
    dp[0][i] = +matrix[0][i];
    max = Math.max(max, dp[0][i]);
  }

  for (let i = 0; i < m; i++) {
    dp[i][0] = +matrix[i][0];
    max = Math.max(max, dp[i][0]);
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === "1") {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;
      }
      max = Math.max(max, dp[i][j]);
    }
  }
  return max * max;
};

时间复杂度O（m * n), 空间复杂度O（m * n）

72. 编辑距离

题目描述

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

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

1
2
3
复制代码插入一个字符
删除一个字符
替换一个字符

例子1

Input: word1 = “horse”, word2 = “ros”

output: 3

解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)

rorse -> rose (删除 ‘r’)

rose -> ros (删除 ‘e’)

例子2

Input:word1 = “intention”, word2 = “execution”

output: 5

解释：
intention -> inention (删除 ‘t’)

inention -> enention (将 ‘i’ 替换为 ‘e’)

enention -> exention (将 ‘n’ 替换为 ‘x’)

exention -> exection (将 ‘n’ 替换为 ‘c’)

exection -> execution (插入 ‘u’)

提示：

1 0 <= word1.length, word2.length <= 500

2 word1 和 word2 由小写英文字母组成

思考

1 已经做了这么多动态规划的题目，很容易想到dp[i][j] 表示word1的i个字符变成word2的j个字符最小距离

接下来就是寻找动态转移方程了

很容易想到有两种情况

当word1[i] 等于word2[j]的时候，

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

当word1[i] 不等于word2[j]的时候，

因为这里有三种操作，
如果增加那么

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

如果删除
dp[i][j] = dp[i-1][j]+1

如果替换
dp[i][j] = dp[i-1][j-1]+1

可以参考实现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
js复制代码/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

// (word1 = "horse"), (word2 = "ros");
// Runtime: 124 ms, faster than 40.13% of JavaScript online submissions for Edit Distance.
// Memory Usage: 42.8 MB, less than 90.97% of JavaScript online submissions for Edit Distance.
export default (word1, word2) => {
  const m = word1.length;
  const n = word2.length;

  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }
  for (let i = 0; i <= n; i++) {
    dp[0][i] = i;
  }
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  // console.log(dp);
  return dp[m][n];
};

时间复杂度O（m * n ）， 空间复杂度O（ m * n）

10. 正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*‘ 的正则表达式匹配。 

1
2
arduino复制代码'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

例子1

Input: s = “aa” p = “a”

output: false

解释：
“a” 无法匹配 “aa” 整个字符串。

例子2

Input: s = “aa” p = “a*“

output: true

解释：
因为 ‘ * ‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

例子3

Input: s = “ab” p = “.*“

output: true

解释：
“.*” 表示可匹配零个或多个（’*’）任意字符（’.’）。

例子4

Input: s = “aab” p = “cab”

output: true

解释：
因为 ‘*‘ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

例子5

Input: s = “mississippi” p = “misis*p\.”

output: false

说明：
1 0 <= s.length <= 20

2 0 <= p.length <= 30

3 s 可能为空，且只包含从 a-z 的小写字母。

4 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 * 。

5 保证每次出现字符 * 时，前面都匹配到有效的字符

思考

1 说实话这题本来还是很有难度的

如果第一次见到该题目，没法实现也很正常

这里那里比较难呢？

难在各种状态如何相互改变，各种条件是否都考虑到了，是否各种情况都考虑到了。

如果单纯看题目，本身其实也不是很难，就是要考虑各种情况，在各种情况下应该如何处理，但是很可能考虑的情况不完全或者考虑错误，很容易就测试用例过不了

这里大体上有两种定义dp[i][j]的定义方法，

一种dp[i][j]表示p的长度i匹配s的长度为j

一种dp[i][j]表示s的长度j匹配p的长度为i

两种思路差不多，但是感觉第一种比较符合逻辑，从下到上匹配比较符合常规思维

这里需要注意的几点是

1 为了考虑s为“”的情况，所以定义了一个dp[p.length + 1][s.length + 1]

这里也说明一种情况，在二维动态规划中一般都是定义这种

刚开始的时候，我本来想定义dp[p.length][s.length]在边界的情况下不是很好处理，所以可以记住以后凡是二维动态规划的时候都定义这种二维数组

2 就是各种情况下的处理，这个确实不是很好处理，但是如何看下代码你会发现很简单

参考实现1

实现2定义dp的方式刚好和实现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
js复制代码/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */

// Runtime: 92 ms, faster than 93.90% of JavaScript online submissions for Regular Expression Matching.
// Memory Usage: 41.5 MB, less than 53.93% of JavaScript online submissions for Regular Expression Matching.
export default (s, p) => {
  const m = p.length;
  const n = s.length;

  const dp = [];

  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(false);
  }

  dp[0][0] = true;

  for (let i = 1; i <= m; i++) {
    if (p[i - 1] === "*") {
      if (i >= 2) {
        dp[i][0] = dp[i - 2][0];
      }
    }
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[i - 1] === ".") {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (p[i - 1] === "*") {
        if (i >= 2) {
          dp[i][j] = dp[i - 2][j] || dp[i - 1][j];
        } else {
          dp[i][j] = dp[i - 1][j];
        }
        if (dp[i][j - 1] && (p[i - 2] === "." || p[i - 2] === s[j - 1])) {
          dp[i][j] = true;
        }
      } else {
        if (p[i - 1] === s[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }
  }

  return dp[m][n];
};

时间复杂度O（n * m）， 空间复杂度O（n * m）

实现2

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
js复制代码/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */

// dp[i][j];
// Runtime: 92 ms, faster than 93.90% of JavaScript online submissions for Regular Expression Matching.
// Memory Usage: 42.1 MB, less than 42.54% of JavaScript online submissions for Regular Expression Matching.
export default (s, p) => {
  const m = s.length;
  const n = p.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(false);
  }

  dp[0][0] = true;

  for (let i = 1; i <= n; i++) {
    if (p[i - 1] == "*") {
      dp[0][i] = dp[0][i - 2];
    }
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      //如果是.则只要dp[i - 1][j - 1] 为true则为true
      if (p[j - 1] == ".") {
        dp[i][j] = dp[i - 1][j - 1];
        // p[j-1]等于字母
      } else if (p[j - 1] != "*") {
        dp[i][j] = dp[i - 1][j - 1] && p[j - 1] == s[i - 1];
        // p[j-1] 等于“*”,
      } else if (p[j - 2] != s[i - 1] && p[j - 2] != ".") {
        dp[i][j] = dp[i][j - 2];
      } else {
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i][j - 2];
      }
    }
  }
  return dp[m][n];
};

时间复杂度O（n * m）， 空间复杂度O（n * m）

0和1背包问题

背包问题是很经典的动态规划问题

有 N 个物品和容量为 W 的背包，每个物品都有
自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物 品只能选择 0 个或 1 个，则问题称为 0-1 背包问题

0和1背包问题如果使用动态规划应该很容易解决，dp[i][j]表示把i个物品放到容量为j的背包的最大的价值

然后就是定义状态转移方程。

这里很容易想到第i件物品，我们只有两种选择，一种是不放入背包中，那么dp[i][j] = dp[i-1][j]

第二种选择就是我们把i件物品放入到背包中，那么
dp[i][j] = dp[i-1][j-wi]+vi,wi是第i件物品的体积，vi是第i件物品的价值，也就是说如果我们把第i件物品放入的时候，那么此时整个背包的价值就等于dp[i-1][j-wi]加上vi（i件物品的价值）。

有了状态转移方程，那么代码就很容易实现了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
js复制代码/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} n
 * @param {number} w
 * @return {number}
 */
export default (weights, valuse, n, w) => {
  const dp = [];
  for (let i = 0; i <= n; i++) {
    dp[i] = new Array(w + 1).fill(0);
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= w; j++) {
      if (j >= weights[i-1]) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i-1]] + valuse[i-1]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][w];
};

时间复杂度O( w * n ),空间复杂度O( w * n )

当然基本上所有的动态规划都可以优化空间，可以看下当二维的时候，如下图

eaa65db96f879d3f7a8330abac561a46.png

此时的状态转移方程是

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + valuse[i]);

可以看到我们当求i=2的状态的时候，只需要记录i=1的状态就可以了，也就是可以使用一维数组表示

假设此时i=1的时候，背包容量分别是1，2，3，4，5的时候的背包价值dp=[2，3，4，5，6]，那么如果求出当i=2的时候的不同体积背包的价值呢，也就是dp的各个位置的值呢

假设此时有一个i物品的体积是2，价值是3<b
此时的还是有两种状态，要么放入i这件物品，要么不放入，

那么此时如何更新dp呢？

可以看到dp[j]要么等于不放入i物品的前一个dp[j]，要么等于放入i物品的时候，dp[i-wi]+vi。

此时状态转移方程是dp[j] =Math.max(dp[j],dp[i-wi]+vi)

但是如果正序修改dp的时候，此时可能发现dp[i-wi]可能已经放入了i物品了。所以状态转移方程就有问题了。

所以必须从后从前遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
js复制代码/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} n
 * @param {number} w
 * @return {number}
 */
export default (weights, valuse, n, w) => {
  const dp = new Array(w + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    for (let j = w; j >= 0; j--) {
      if (j >= weights[i-1]) {
        dp[j] = Math.max(dp[j], dp[j - weights[i-1]] + valuse[i-1]);
      }
    }
  }
  return dp[w];
};

时间复杂度O(w * n ),空间复杂度O(w )

416. 分割等和子集

题目描述

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

注意：

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

例子1

Input: [1, 5, 11, 5]

output: true

解释： 数组可以分割成 [1, 5, 5] 和 [11].

例子2

Input: [1, 2, 3, 5]

output: false

解释： 数组不能分割成两个元素和相等的子集.

思考

1 这里要转换成0和1背包问题，其实还是有些难度，如何想到如何转换成0和1背包就按照0和1背包问题解决就可以了

主要是问题是一共有nums.length个数字，每个数字就涉及到选择或者不选择，这些可以当做0和1背包的物品

那么什么当做0和1背包的体积呢？

这是比较关键的，想下什么可以当做0和1背包的体积

这里一个比较重要的转换是就是所有数字的和的一半可以当做背包的体积。

我们选择任何数字，只要和等于所有数字的和的一半就可以了

这样就转换成了0和1背包的问题了

没有优化空间的，可以看下实现1

优化空间的，可以看下实现2

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {boolean}
 */
// [1,5,11,5]
// 155 11
// 1235

// [1, 2, 3, 5];
// [1, 1, 2, 2];
// Runtime: 244 ms, faster than 45.49% of JavaScript online submissions for Partition Equal Subset Sum.
// Memory Usage: 70.8 MB, less than 31.03% of JavaScript online submissions for Partition Equal Subset Sum.
export default (nums) => {
  const len = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 !== 0) return false;
  const target = sum / 2;
  const dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(target + 1).fill(false);
  }
  for (let i = 0; i < len; ++i) {
    dp[i][0] = true;
  }
  for (let i = 1; i < len; i++) {
    for (let j = 0; j <= target; ++j) {
      if (j >= nums[i - 1]) {
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
      if (j === target && dp[i][j]) {
        return true;
      }
    }
  }
  // console.log(dp);
  return dp[len - 1][target];
};

时间复杂度O（n^2）， 空间复杂度O（n^2）

实现2

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
js复制代码/**
 * @param {number[]} nums
 * @return {boolean}
 */
// [1,5,11,5]
// 155 11
// 1235

// [1, 2, 3, 5];
// [1, 1, 2, 2];
// Runtime: 108 ms, faster than 91.72% of JavaScript online submissions for Partition Equal Subset Sum.
// Memory Usage: 40.9 MB, less than 75.58% of JavaScript online submissions for Partition Equal Subset Sum.
export default (nums) => {
  const len = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 !== 0) return false;
  const target = sum / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i < len; i++) {
    for (let j = target; j >= 0; j--) {
      if (j >= nums[i - 1]) { 
        dp[j] = dp[j] || dp[j - nums[i - 1]];
      } else {
        dp[j] = dp[j];
      }
      if (j === target && dp[j]) {
        return true;
      }
    }
  }
  // console.log(dp);
  return dp[target];
};

时间复杂度O（n^2）， 空间复杂度O（n^2）

494. 目标和

题目描述

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

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

例子1

Input: nums: [1, 1, 1, 1, 1], S: 3

output: 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
yaml复制代码数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。

思考

1 这里也是典型的0和1背包问题变形，也就是要么选择+nums[i]或者选择-nums[i]

状态转移方程也好解决 

1
2
3
4
5
6
7
ini复制代码if (j + nums[i - 1] < maxN) {
    dp[i][j] += dp[i - 1][j + nums[i - 1]];
}
// 选择+nums[i - 1]
if (j - nums[i - 1] >= 0) {
    dp[i][j] += dp[i - 1][j - nums[i - 1]];
}

这里的难点是如何处理负数的情况？

如果没想清楚，可以看下代码，其实就是定义所有数据的和的两倍大小，这样就保证了-sum到sum都能包含进去

另外就是如何表示负数，刚开始的时候，我是想是否小于sum，来确定不同的状态转移方程，因为当是负数的情况下，状态转移方程是不一样的

比如nums: [1, 1, 1, 1, 1], S: 3
当求dp[2][5] = dp[1][4]+dp[1][6],但是实际上是不正确的，因为j<=sum的时候实际上表示的是负数

后来看了题解，原来是把当j=sum的时候表示0，j等于sum+1的时候表示正数1，当j等于sum-1的时候表示-1，这样就特别容易处理了

这里可以学习到表示从-sum到sum如何使用数组表示的方法

可以参考实现1

空间优化，参考实现2

实现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
js复制代码/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */

// Runtime: 176 ms, faster than 76.29% of JavaScript online submissions for Target Sum.
// Memory Usage: 44.4 MB, less than 52.32% of JavaScript online submissions for Target Sum.
export default (nums, S) => {
  let sum = 0;
  for (let i of nums) {
    sum += i;
  }

  // 如果大于最大的和小于最小的
  if (S > sum || S < -sum) {
    return 0;
  }
  const dp = [];
  const len = nums.length;
  const maxN = 2 * sum + 1;
  for (let i = 0; i <= len; i++) {
    dp[i] = new Array(maxN).fill(0);
  }
  // 这里指全部选择负数的时候，只有一种选择
  dp[0][0 + sum] = 1;
  for (let i = 1; i <= nums.length; i++) {
    for (let j = 0; j < maxN; j++) {
      // 选择-nums[i - 1]
      if (j + nums[i - 1] < maxN) {
        dp[i][j] += dp[i - 1][j + nums[i - 1]];
      }
      // 选择+nums[i - 1]
      if (j - nums[i - 1] >= 0) {
        dp[i][j] += dp[i - 1][j - nums[i - 1]];
      }
    }
  }
  // console.log(dp);
  return dp[nums.length][sum + S];
};

时间复杂度O（n * m）， 空间复杂度O（n * m）

实现2

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
js复制代码/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */

// Runtime: 96 ms, faster than 96.39% of JavaScript online submissions for Target Sum.
// Memory Usage: 44.7 MB, less than 41.49% of JavaScript online submissions for Target Sum.
export default (nums, S) => {
  let sum = 0;
  for (let i of nums) {
    sum += i;
  }

  //
  if (S > sum || S < -sum) {
    return 0;
  }
  const len = 2 * sum + 1;
  let dp = new Array(len).fill(0);
  // 所有都选择负数
  dp[sum] = 1;

  for (let i = 0; i < nums.length; i++) {
    const next = new Array(len).fill(0);
    for (let k = 0; k < len; k++) {
      if (dp[k] != 0) {
        // 如果k有n中选择，那么当选择+ nums[i]的时候，肯定有n种，当选择- nums[i]的时候，肯定也有n种
        next[k + nums[i]] += dp[k];
        next[k - nums[i]] += dp[k];
      }
    }
    dp = next;
  }
  return dp[sum + S];
};

时间复杂度O（n * m）， 空间复杂度O（n ）

474. 一和零

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

例子1

Input: strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3

output: 4

解释： 最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

例子2

Input: strs = [“10”, “0”, “1”], m = 1, n = 1

output: 2

解释： 最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

1 1<= strs.length <= 600

2 1<= strs[i].length <= 100

3 strs[i] 仅由 ‘0’ 和 ‘1’ 组成

4 <= m, n <= 100

思考

1 这里题目感觉还是比较难的，如果是第一次接触，直接看答案就可以

这里涉及到一个三维数组，这种解法虽然说是0和1背包问题，但是实际上如果你理解为递归更容易理解

假设我们有一个函数memo是计算strs[i]开始的返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1

所以此时就有两种选择，要么加入strs[i]，要么不加入strs[i]，所以这里状态改变方程就是

Math.max(1 + memo(i), memo(i));

可以看下实现1

2 第二种方法就是定义dp[m][n] 表示已经遍历过strs从0到i的最大的子集的长度

那么状态转移方程是啥？

这里是三维降低到二维，可以类比想一下0和1背包问题从二维降低到一维的情况

所以这里dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]) (zeros 表示strs[i]中0的长度， ones表示表示strs[i]中1的长度)

可以参考实现2

实现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
js复制代码/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

// ["10", "0001", "111001", "1", "0"];
// 5;
// 3;

// ["011111", "001", "001"], 4, 5;
const memo = (dp, start, m, n, size, strs) => {
  if (start >= size || m < 0 || n < 0) return 0;
  if (m === 0 && n === 0) return 0;
  // console.log(dp[start][m], start, m, n);
  if (dp[start][m][n] != -1) return dp[start][m][n];

  let res = 0;
  let i = start;
  let ones = 0;
  for (let k1 = 0; k1 < strs[i].length; k1++) {
    if (strs[i][k1] === "1") {
      ones++;
    }
  }
  let zeros = strs[i].length - ones;
  if (zeros <= m && ones <= n) {
    // 如果选择，则选择其中选择或者不选择中的最大的
    res = Math.max(1 + memo(dp, i + 1, m - zeros, n - ones, size, strs), memo(dp, i + 1, m, n, size, strs));
  } else {
    // 如果不符合规则，则直接下一个
    res = memo(dp, i + 1, m, n, size, strs);
  }
  dp[start][m][n] = res;
  return res;
};
// Runtime: 496 ms, faster than 34.21% of JavaScript online submissions for Ones and Zeroes.
// Memory Usage: 103 MB, less than 28.95% of JavaScript online submissions for Ones and Zeroes.
export default (strs, m, n) => {
  const len = strs.length;
  const dp = [];
  for (let i = 0; i < len; i++) {
    dp[i] = [];
    for (let k = 0; k <= m; k++) {
      dp[i][k] = new Array(n + 1).fill(-1);
    }
  }
  return memo(dp, 0, m, n, len, strs);
};

时间复杂度O（strs的长度 * strs[i]的长度）， 空间复杂度O（strs的长度 * m * n）

实现2

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
js复制代码/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

// Runtime: 140 ms, faster than 92.11% of JavaScript online submissions for Ones and Zeroes.
// Memory Usage: 40.9 MB, less than 78.95% of JavaScript online submissions for Ones and Zeroes.
export default (strs, m, n) => {
  const len = strs.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }

  for (let i = 0; i < len; i++) {
    let ones = 0;
    for (let k1 = 0; k1 < strs[i].length; k1++) {
      if (strs[i][k1] === "1") {
        ones++;
      }
    }
    let zeros = strs[i].length - ones;
    for (let k2 = m; k2 >= zeros; --k2) {
      for (let j = n; j >= ones; --j) {
        dp[k2][j] = Math.max(dp[k2][j], 1 + dp[k2 - zeros][j - ones]);
      }
    }
  }
  return dp[m][n];
};

时间复杂度O（strs.length * m * n）， 空间复杂度O（m * n）

完全背包问题

有 N 个物品和容量为 W 的背包，每个物品都有
自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品可以选择多次，那么这里就是完全背包问题

完全背包问题和0和1背包问题差不多，解决思路也是类似，dp[i][j]表示把i个物品放到容量为j的背包的最大的价值

然后就是定义状态转移方程。

这里很容易想到第i件物品，在0和1背包的时候，我们只有两种选择，但是在完全背包的时候，我们是有多种选择的，要么选择一次，要么选择两次，要么选择三次，如果背包体积无穷大，我们甚至可以选择无数次

那么状态方程如何确定呢？

很容易想到

dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wi*k]+vi * k) k>=1 && wi * k <=j

但是还是很复杂，不是很好解决

3651c5000d7b865c4e80b339c5e45d73.png

可以看下上图，此时
dp[2][5] = Math.max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)

那么应该如何改进上面的状态转移方程呢？

此时我们可以改下上面的状态转移方程，变成如下

dp[2][5] = Math.max(dp[1][5], Math.max(dp[1][3] , dp[1][1] + 3) + 3)

然后又以为知道

dp[2][3]= Math.max(dp[1][3] , dp[1][1] + 3)

所以此时

dp[2][5] = Math.max(dp[1][5],dp[2][3] + 3)

类似下图：

f8ae7d2aaa4bf1f21e49d3123cda9888.png

所以最后状态转移方程变成了

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-wi]+vi)

代码如下：

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
js复制代码/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} n
 * @param {number} w
 * @return {number}
 */
export default (weights, valuse, n, w) => {
  const dp = [];
  for (let i = 0; i <= n; i++) {
    dp[i] = new Array(w + 1).fill(0);
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= w; j++) {
      // 如果选择，
      if (j >= weights[i - 1]) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + valuse[i - 1]);
      } else {
        //如果不选择
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][w];
};

类似于0和1背包，这里也可以进行空间压缩，可以看下下图，这里也只需要使用一维数组就可以了,但是注意这里是使用了正向遍历

d45486323001474fc1356bcd90ec425f.png

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
js复制代码/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} n
 * @param {number} w
 * @return {number}
 */
export default (weights, valuse, n, w) => {
  const dp = new Array(w + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= w; j++) {
      // 如果选择，
      if (j >= weights[i - 1]) {
        dp[j] = Math.max(dp[j], [j - weights[i]] + valuse[i]);
      }
    }
  }
  return dp[w];
};

322. 零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

例子1

Input: coins = [1, 2, 5], amount = 11

output: 3

解释： 11 = 5 + 5 + 1。

例子2

Input:coins = [2], amount = 3

output: -1

例子3

Input:coins = [1], amount = 0

output: 0

例子4

Input:coins = [1], amount = 1

output: 1

例子5

Input:coins = [1], amount = 2

output: 2

提示：

1 1 <= coins.length <= 12

2 1 <= coins[i] <= 2^31 - 1

3 0 <= amount <= 10^4

思考

1 这是典型的完全背包问题，所以可以直接按照完全背包来解决就可以了

这里的技巧就是因为需要寻找最小的个数，所以应该如何设置最大数值呢？

可以看下代码中如何设置的

另外这里可能还要一点就是如何设置边界情况，就是二维数组dp
当i=0和当j=0的时候，应该如何设置？

这里如何边界情况设置不对的话，下面的测试用例是不过的

[186, 419, 83, 408], 6249 结果是20

其它的都比较简单，可以参考实现1

2 这里也可以优化空间，优化空间有个技巧，就是自己画图，把dp的图每步的画出来，可以看下那些不需要，那些需要，就很容易可以看出那些可以优化

这里可能状态转移
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1) 有点不是很好理解

很多人认为得是dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1， dp[i-2* coins[j]] +2 …) 一直到0

其实这里dp[i - coins[j]] 已经包含后面的情况

比如这里coins[j] =2 ,如果按照这个

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

dp[5]= Math.min(dp[5], dp[3]+1， dp[1]+2)

然后会发现
dp[5]= Math.min(dp[5], (dp[3]， dp[1]+1) + 1 )
而dp[3] = Math.min(dp[3]， dp[1]+1),所以还是转换为了
dp[5]= Math.min(dp[5], dp[3]+1)

可以参考实现2

实现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
js复制代码/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
// Runtime: 184 ms, faster than 25.00% of JavaScript online submissions for Coin Change.
// Memory Usage: 44.9 MB, less than 19.34% of JavaScript online submissions for Coin Change.
export default (coins, amount) => {
  const len = coins.length;
  const max = amount + 1;
  const dp = [];
  if (amount === 0) return 0;
  for (let i = 0; i <= len; i++) {
    dp[i] = new Array(max).fill(max);
  }
  // coins.sort((a, b) => a - b);
  for (let i = 0; i <= len; i++) {
    dp[i][0] = 0;
  }
  for (let i = 0; i <= amount; i++) {
    dp[0][amount] = max;
  }
  for (let i = 1; i <= len; i++) {
    for (let j = 0; j <= amount; j++) {
      if (j >= coins[i - 1]) {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  return dp[len][amount] === max ? -1 : dp[len][amount];
};

时间复杂度O（m * n ）， 空间复杂度O（ m * n）

实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
js复制代码/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
// [1, 2, 5], 11;
// Runtime: 124 ms, faster than 63.93% of JavaScript online submissions for Coin Change.
// Memory Usage: 42.7 MB, less than 88.09% of JavaScript online submissions for Coin Change.
export default (coins, amount) => {
  const Max = amount + 1;
  const dp = new Array(amount + 1).fill(Max);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (i >= coins[j]) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
};

时间复杂度O（ m * n）， 空间复杂度O（n）

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%