算法-js系列(2):动态规划-中等(1)

作者：黑客灵魂 | 2024-07-09 03:56:07

踩

刷动态规划的题，感觉简单、中等的区分度没有这么高，都是能想到状态表示和状态转移方程就做的出来，想不出来就做不出来，所以重点还是在多做多想

文章目录

~~跳过了两道别的方法的题~~

5_最长回文子串

最长回文子串问题（五种方法）

// 上面的，最长公共子串方法（字符串反转后和原字符串的最长公共子串就是最长回文子串 。）是错的
// abdeba
// abedba
// 最长公共子串为 2，但最长回文子串为 1
1
2
3
4

/*
leetcode 5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。

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

示例 2：
输入：s = "cbbd"
输出："bb"

示例 3：
输入：s = "a"
输出："a"

示例 4：
输入：s = "ac"
输出："a"

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和 / 或小写）组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
 * @param {string} s
 * @return {string}
 */

// 动态规划
var longestPalindrome = function(s) {
  // f[i] - s[0~i] 中，以第 i 个字符为结尾的回文子串的最大长度
  // 状态转移 - 
  // f[i - 1] + 2 (s[i] === s[i - f[i-1] - 1])
  // f[i - 1] + 1 (f[i - 1] === 1 && s[i] === s[i - 1]])
  // ... 无法转移

  // f[i][j] - s[i~j] 是不是一个回文串（i<=j）
  // 状态转移 
  // f[i][j] = f[i+1][j-1] && s[i] == s[j]
  // 初始化
  // 回文串长 1：f[i][i] = true
  // 回文串长 2：f[i][j] = (s[i] === s[j]) j=i+1
  const n = s.length
  // 定义 f 并初始化为 false
  const f = new Array(n + 5).fill(0).map(() => new Array(n + 5).fill(false))

  // 在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。
  // let res = ''
  let res = [0, 0, 0]
  for (let i = 0; i < n; i++) {
    // i - 字符串长度-1
    for (let j = 0; j + i < n; j++) {
      // j - 字符串的起始位置
      const k = i + j
      // k - 字符串的终止位置
      if (i === 0) { // 字符串长 1
        f[j][k] = true
      } else if (i === 1) { // 字符串长 2
        f[j][k] = (s[j] === s[k])
      } else { // 字符串的长大于 2
        f[j][k] = f[j + 1][k - 1] && (s[j] === s[k])
      }
      // 记录最长的回文子串
      // if (f[j][k] && i + 1 > res.length) {
      //   res = s.slice(j, k + 1) // slice 不会影响性能，性能反而要好点
      // }
      // 怕 slice 影响了性能，试着只是记录最长回文子串的起止位置和长度
      if (f[j][k] && i + 1 > res[2]) {
        res[0] = j
        res[1] = k
        res[2] = k - j + 1
      }
    }
  }
  return s.slice(res[0], res[1] + 1)
}

// 中心扩展法
// 枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。
var longestPalindrome1 = function(s) {
  const n = s.length
  // 扩展函数
  function expandAroundCenter(s, l, r) {
    while (l >= 0 && r < n && s[l] === s[r]) {
      l--
      r++
    }
    return [l + 1, r - 1] // 返回回文串的左右位置
  }

  let start = end = 0
  for (let i = 0; i < n; i++) {
    // 对长度为 1 的回文串进行扩展
    const [l1, r1] = expandAroundCenter(s, i, i)
    // 对长度为 2 的回文串进行扩展
    const [l2, r2] = expandAroundCenter(s, i, i + 1)
    // 更新最长回文子串
    if (r1 - l1 > end - start) {
      start = l1
      end = r1
    }
    if (r2 - l2 > end - start) {
      start = l2
      end = r2
    }
  }
  // 返回最长回文子串
  return s.slice(start, end + 1)
}

// Manacher 算法
// 使用臂长的概念，优化中心扩展法，跳过部分不需要比较的字符

var s = "babad"
const res = longestPalindrome(s)
console.log(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

62_不同路径

62_不同路径-官方

62_不同路径-精选

/*
leetcode 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

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

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

示例 1：
![](https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png)
输入：m = 3, n = 7
输出：28

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

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

示例 4：
输入：m = 3, n = 3
输出：6

提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
// 动态规划
var uniquePaths = function(m, n) {
  // f(i, j) - 走到 (i, j) 共有的路径数
  // 状态转移 - 最后一步是向下/右
  // f(i, j) = f(i - 1, j) + f(i, j - 1)
  // 将最上/左方初始化为 1（偷懒全部初始化为 1）
  const f = new Array(m + 5).fill(0).map(() => new Array(n + 5).fill(1))
  // 只计算第 2 行/列之后的
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = f[i - 1][j] + f[i][j - 1]
    }
  }
  return f[m-1][n-1]
};

// 动态规划 - 空间优化
// f(i, j) 仅与第 i 行和第 i-1 行的状态有关，可使用滚动数组思想降低空间复杂度
var uniquePaths1 = function(m, n) {
  // m n 具有交换性，让 m 一直是较小的那个
  [m, n] = [Math.min(m, n), Math.max(m, n)]
  // console.log(m, n)
  let pre = new Array(m + 5).fill(1)
  let cur = new Array(m + 5).fill(1)
  // 只计算第 2 行/列之后的
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) { // j 就是遍历 m 了
      cur[j] = pre[j] + cur[j - 1]
    }
    pre = cur
  }
  return pre[m-1]
};

// 动态规划 - 空间优化（进一步优化）
var uniquePaths1 = function(m, n) {
  // m n 具有交换性，让 m 一直是较小的那个
  [m, n] = [Math.min(m, n), Math.max(m, n)]
  let cur = new Array(m + 5).fill(1)
  // 只计算第 2 行/列之后的
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) { // j 就是遍历 m 了
      cur[j] += cur[j - 1]
    }
  }
  return cur[m-1]
};

var m = 3, n = 7
// var m = 7, n = 3
// var m = 3, n = 2
// var m = 3, n = 3
const res = uniquePaths(m, n)
console.log(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

63_不同路径II

/*
leetcode 63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

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

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

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

示例 1：
![](https://assets.leetcode.com/uploads/2020/11/04/robot1.jpg)
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：
![](https://assets.leetcode.com/uploads/2020/11/04/robot2.jpg)
输入：obstacleGrid = [[0,1],[0,0]]
输出：1

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */

// 动态规划 
var uniquePathsWithObstacles = function(obstacleGrid) {
  // f(i, j) - 走到 (i, j) 共有的路径数
  // 状态转移 - 最后一步是向下/右
  // f(i, j) = f(i - 1, j) + f(i, j - 1)
  // 将最上/左方初始化为 1（不能这样初始化了，因为有障碍物后面的点不可达）
  // 有障碍物处的 f(i, j) 始终为 0
  const m = obstacleGrid.length
  const n = obstacleGrid[0].length
  // 出发点或终点有障碍物，直接返回 0——不特判也能得到正确结果
  if (obstacleGrid[0][0] === 1 || obstacleGrid[m-1][n-1] === 1) {
    return 0
  }

  // 不同的初始化方式
  // const f = new Array(m).fill(0).map(() => new Array(n).fill(1))

  // // 所有有障碍的地方初始化为 0
  // obstacleGrid.forEach((item, i) => {
  //   item.forEach((x, j) => {
  //     if (item[j] === 1) {
  //       f[i][j] = 0
  //     }
  //   })
  // })

  // // 第 0 行中，若出现障碍物，则此后的点均初始化为 0
  // for (let i = 0; i < n; i++) {
  //   if (obstacleGrid[0][i] === 1) {
  //     for (let j = i; j < n; j++) {
  //       f[0][j] = 0
  //     }
  //     break
  //   }
  // }

  // // 第 0 列中，若出现障碍物，则此后的点均初始化为 0
  // for (let i = 0; i < m; i++) {
  //   if (obstacleGrid[i][0] === 1) {
  //     for (let j = i; j < m; j++) {
  //       f[j][0] = 0
  //     }
  //     break
  //   }
  // }

  // 也可以先全部初始化为 0，然后将初始可达的点置为 1
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0))

  // 第 0 行中，若未出现障碍物，则点均初始化为 1
  for (let i = 0; i < n; i++) {
    if (obstacleGrid[0][i] === 1) {
      break
    }
    f[0][i] = 1
  }

  // 第 0 列中，若出现障碍物，则此后的点均初始化为 0
  for (let i = 0; i < m; i++) {
    if (obstacleGrid[i][0] === 1) {
      break
    }
    f[i][0] = 1
  }

  // 只计算第 1 行/列之后的
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (obstacleGrid[i][j] !== 1) {
        f[i][j] = f[i - 1][j] + f[i][j - 1]
      }
    }
  }

  return f[m-1][n-1]
};

// 动态规划 - 空间优化（滚动数组思想）
// 懒得敲了

var obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
var obstacleGrid = [[0,1],[0,0]]
var obstacleGrid = [[1, 0]]
var obstacleGrid = [[0,0],[1,1],[0,0]]

const res = uniquePathsWithObstacles(obstacleGrid)
console.log(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

64_最小路径和

64_最小路径和-官方

64_最小路径和-精选

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

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

示例 1：
![](https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg)
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
 * @param {number[][]} grid
 * @return {number}
 */

// 动态规划
var minPathSum = function(grid) {
  // f(i, j) - 到达点 (i, j) 的路径上数字总和的最小值
  // 状态转移 - 最后一步向下/右
  // f(i, j) = min(f(i - 1, j), f(i, j - 1)) + grid(i, j)
  const m = grid.length // [][0]
  const n = grid[0].length // [0][]
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0))
  let sum = 0
  for (let i = 0; i < m; i++) {
    sum += grid[i][0]
    f[i][0] = sum
  }
  sum = 0
  for (let i = 0; i < n; i++) {
    sum += grid[0][i]
    f[0][i] = sum
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j]
    }
  }
  return f[m - 1][n - 1]
}

// 动态规划 - 空间优化（滚动数组）
// 空间小了 0.3MB 时间短了 4 ms
var minPathSum = function(grid) {
  // f(i, j) - 到达点 (i, j) 的路径上数字总和的最小值
  // 状态转移 - 最后一步向下/右
  // f(i, j) = min(f(i - 1, j), f(i, j - 1)) + grid(i, j)
  const m = grid.length // [][0]
  const n = grid[0].length // [0][]
  // [m, n] = [Math.min(m, n), Math.max(m, n)]
  let cur = new Array(n).fill(0)
  cur[0] = grid[0][0]
  // 第一行的每列路径，全部记录下来
  for (let i = 1; i < n; i++) {
    cur[i] = cur[i - 1] + grid[0][i]
  }
  for (let i = 1; i < m; i++) {
    // 第一列的每行累加
    cur[0] += grid[i][0]
    for (let j = 1; j < n; j++) {
      cur[j] = Math.min(cur[j], cur[j - 1]) + grid[i][j]
    }
  }
  return cur[n - 1]
}

var grid = [[1,3,1],[1,5,1],[4,2,1]] // 7
grid = [[1,2,3],[4,5,6]] // 12
const res = minPathSum(grid)
console.log(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

91_解码方法

91_解码方法-民间

/*
leetcode 91. 解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"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）。

示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

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

示例 4：
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串开头的 0 无法指向一个有效的字符。 

提示：
1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
 * @param {string} s
 * @return {number}
 */

// 动态规划
var numDecodings = function(s) {
  // f(i) - 以 s[i] 结尾的字符串，的解码总数
  // 状态转移 - 最后一步，解码一/两个字符
  if (s[0] == 0) {
    return 0
  }
  const len = s.length
  const f = new Array(len + 1).fill(0)
  f[0] = 1
  f[1] = 1
  for (let i = 2; i <= len; i++) {
    if (s[i - 1] != 0) {
      f[i] = f[i - 1]
    }
    let num = s.slice(i - 2, i)
    num = parseInt(num)
    // console.log(num)
    if (num >= 10 && num <= 26) {
      f[i] += f[i - 2]
    }
  }
  return f[len]
}

// 动态规划 - 空间优化（滚动数组）
// 空间减小了 0.1MB 时间增加了 20 ms
var numDecodings = function(s) {
  // f(i) - 以 s[i] 结尾的字符串，的解码总数
  // 状态转移 - 最后一步，解码一/两个字符
  // f(i) = f(i - 1) + f(i - 2)
  // 条件：s[i] != 0， s[i-1, i] 在 [10, 26] 之间
  if (s[0] == 0) {
    return 0
  }
  const len = s.length
  let pre = 1
  let cur = 1
  for (let i = 2; i <= len; i++) {
    let tmp = 0
    if (s[i - 1] != 0) {
      tmp = cur
    }
    let num = s.slice(i - 2, i)
    num = parseInt(num)
    // console.log(num)
    if (num >= 10 && num <= 26) {
      tmp += pre
    }
    pre = cur
    cur = tmp
  }
  return cur
}

var s = "06" // 0
var s = "12" // 2
var s = "226" // 3
const res = numDecodings(s)
console.log(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

96_不同的二叉搜索树

96_不同的二叉搜索树-官方

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

示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/**
 * @param {number} n
 * @return {number}
 */
// 动态规划
var numTrees = function(n) {
  // G(n) - 序列长度为 n 的二叉搜索树的种数
  // f(i, n) - 以 i 为根结点，序列长度为 n 的二叉搜索树的种数
  // 状态转移 - 不同根结点构成所有二叉搜索树
  // G(n) = f(1, n) + f(2, n) + ... + f(n, n)
  // f(i, n) = G(i - 1)G(n - i) =>
  // G(n) = G(0)G(n-1) + G(1)G(n-2) + ... + G(n-1)G(0)
  // let g = [] // 必须初始化为 0，这样声明，里面的值是 undefined，无法计算
  // console.log(g[0]) // undefined
  let g = new Array(n + 1).fill(0)
  g[0] = 1
  g[1] = 1
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      g[i] += g[j - 1] * g[i - j]
    }
  }
  return g[n]
}

// G(n) = G(0)G(n-1) + G(1)G(n-2) + ... + G(n-1)G(0) —— 卡塔兰数 C_n
// C0 = 1，C_(n+1)=2(2n+1)/(n+2) C_n

var n = 10
const res = numTrees(n)
console.log(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

推导出来的 G(n) 的公式 $\sum_{i=1}^{n}F(i, n),G(0)=1, G(1)=1$

上述即为 卡塔兰数 $G_{n+1} = \frac{2(2n+1)}{n+2} C_n,C_0=1$

95_不同的二叉搜索树II

这题也不是动态规划呀，先搁着，以后写递归的时候再回头来看（搁置？?）

/*
leetcode 95. 不同的二叉搜索树 II
给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

示例：
输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

提示：
0 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(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
33
34
35
36
37
38
39
40
41
42
43
44
45

97_交错字符串

97_交错字符串-官方

「手画图解」DFS 回溯及其优化

这个 DFS 回溯讲的很清晰，到时候做 DFS 回溯板块的时候，要回来看

/*
leetcode 97. 交错字符串
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
提示：a + b 意味着字符串 a 和 b 连接。 

示例 1：
![](https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg)
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/interleaving-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
// 动态规划
var isInterleave = function(s1, s2, s3) {
  // 能决定下一步的是？现在选择的是哪个字符串，另一个字符串从哪里选择
  // f(i, j) - s3[i~] 是从 j(0/1) 字符串选择的
  // 放弃
  
  // 上面的思路错了——不用管交错的，直接一个字符一个字符接着匹配就行
  // 主要是看 s3 的字符能不能和 s1/s2 的字符匹配
  // f(i, j) - s1[1~i] 和 s2[1~j] 能否交错组成 s3[1~i+j]
  // 状态转移 - s3[i+j] 最后是和谁匹配的 s1[i] 还是 s2[j]
  // (f(i - 1, j) && s1[i] === s3[i + j]) || (f(i, j - 1) && s2[j] === s3[i + j])
  const len1 = s1.length
  const len2 = s2.length
  if (len1 + len2 !== s3.length) {
    return false
  }
  const f = new Array(len1 + 5).fill(false).map(() => new Array(len2 + 5).fill(false))
  // f[0, x] f[x, 0] 都要初始化出来 f[0, 0]-用不到，可以不管
  f[0][0] = true // 如果传入的都是空串，就要初始化 f[0, 0]

  // 初始化复杂了 - 动态转移不从 1 开始，从 0 开始
  // for (let i = 1; i <= len1; i++) {
  //   f[i][0] = (s1[i - 1] === s3[i - 1])
  //   if (f[i][0] === false) { // 有字符不匹配了，后面的就不可能匹配上
  //     break
  //   }
  // }
  // for (let i = 1; i <= len2; i++) {
  //   f[0][i] = (s2[i - 1] === s3[i - 1])
  //   if (f[0][i] === false) {
  //     break
  //   }
  // }
  // for (let i = 1; i <= len1; i++) {
  //   for (let j = 1; j <= len2; j++) {
  //     const x = i - 1, y = j - 1
  //     f[i][j] = (f[i - 1][j] && (s1[x] === s3[x + y + 1])) || (f[i][j - 1] && (s2[y] === s3[x + y + 1]))
  //   }
  // }

  // 动态转移不从 1 开始，从 0 开始
  for (let i = 0; i <= len1; i++) {
    for (let j = 0; j <= len2; j++) {
      const x = i - 1, y = j - 1
      if (i > 0) { // 这里就要加上自己去或了
        f[i][j] = f[i][j] || (f[i - 1][j] && (s1[x] === s3[x + y + 1]))
      }
      if (j > 0) {
        f[i][j] = f[i][j] || (f[i][j - 1] && (s2[y] === s3[x + y + 1]))
      }
    }
  }
  return f[len1][len2]
}

// 动态规划 - 空间优化（滚动数组的思想）
// 空间小了 3MB 时间多了 4ms 
// 老实说，懂了滚动数组的思想，但单独写代码写不出来，只能按照未优化的代码去改写
var isInterleave = function(s1, s2, s3) {
  // 不用管交错的，直接一个字符一个字符接着匹配就行
  // 主要是看 s3 的字符能不能和 s1/s2 的字符匹配
  // f(i, j) - s1[1~i] 和 s2[1~j] 能否交错组成 s3[1~i+j]
  // 状态转移 - s3[i+j] 最后是和谁匹配的 s1[i] 还是 s2[j]
  // (f(i - 1, j) && s1[i] === s3[i + j]) || (f(i, j - 1) && s2[j] === s3[i + j])
  const len1 = s1.length
  const len2 = s2.length
  if (len1 + len2 !== s3.length) {
    return false
  }
  const cur = new Array(len2 + 5).fill(false)
  cur[0] = true

  // 动态转移不从 1 开始，从 0 开始
  for (let i = 0; i <= len1; i++) {
    for (let j = 0; j <= len2; j++) {
      const x = i - 1, y = j - 1
      if (i > 0) {
        cur[j] = cur[j] && (s1[x] === s3[x + y + 1])
      }
      if (j > 0) {
        cur[j] = cur[j] || (cur[j - 1] && (s2[y] === s3[x + y + 1]))
      }
    }
  }
  return cur[len2]
}

var s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" // true
var s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" // false
var s1 = "", s2 = "", s3 = "" // true
var s1 = "db", s2 = "b", s3 = "cbb" // false
const res = isInterleave(s1, s2, s3)
console.log(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

120_三角形最小路径和

递归 + 记忆化 + DP，

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/801345