HOW - DP 动态规划系列（二）

通过几个算法的学习，加深理解和掌握动态规划。

一、不同路径1

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

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

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

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

示例2：
输入：m = 2, n = 3
输出：3

解释： 从左上角开始，总共有 3 条路径可以到达右下角：

• 向右 -> 向右 -> 向下
• 向右 -> 向下 -> 向右
• 向下 -> 向右 -> 向右

根据场景分析，想要走到右下角的终点，它的前一条路径来源只有两种，上方或者左方：

每一个网格都是一样的，那其实就有一个状态转移的过程，可以考虑动态规划求解。

相比系列一遇到的问题，这个问题想要利用动态规划，dp[] 是需要构造二维的才行。

const uniquePaths = (m, n) => {
	// m: row
	// n: column

	// 1. 确定 dp[i][j] 含义：到达网格 [row=i][column=j] 的路径数目
	// 2. 确定递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1] 即 dp[i][j]都是从其上方和左方推导而来
	// 3. 初始化：dp[i][0] 都是1 dp[0][j] 也都是1 这些位置一定只有1条路径
	// 4. 遍历顺序：从左到右一层一层遍历即可
	// 5. 打印 dp[]
	const dp = Array(m).fill().map(item => Array(n));
	for (let i = 0; i < m; i++) {
		dp[i][0] = 1;
	}
	for (let j = 0; j < n; j++) {
		dp[0][j] = 1;
	}
	for (let i = 1; i < m; i++) {
		for (let j = 1; j < n; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		}
	}
	return dp[m - 1][n - 1];
}
console.log(uniquePaths(3, 7)); // 28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二、不同路径2

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

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

• 向右 -> 向右 -> 向下 -> 向下
• 向下 -> 向下 -> 向右 -> 向右

根据场景分析，有障碍相比没有障碍的情况，无非就是对应的 dp[i][j] = 0，即走不通。

const uniquePaths = (obstacleGrid) => {
	const m = obstacleGrid.length;
	const n = obstacleGrid[0].length;

	const dp = Array(m).fill().map(item => Array(n));
	for (let i = 0; i < m; i++) {
		// 有阻碍之后剩下的就不用赋值了 通通为0
		if (obstacleGrid[i][0] === 1) {
			break;
		}
		dp[i][0] = 1;
	}
	for (let j = 0; j < n; j++) {
		// 有阻碍之后剩下的就不用赋值了 通通为0
		if (obstacleGrid[0][j] === 1) {
			break;
		}
		dp[0][j] = 1;
	}
	for (let i = 1; i < m; i++) {
		for (let j = 1; j < n; j++) {
			dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
		}
	}
	return dp[m - 1][n - 1];
}
console.log(uniquePaths([[0,0,0],[0,1,0],[0,0,0]])); // 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

三、整数拆分

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

示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2：
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

这个问题应该直击要害，应该尽量拆成数值近似相等的几个数，这样才会得到最大的乘积。比如 10 = 3 + 3 + 4 比 10 = 5 + 5 好。

进一步分析，对于 10，依赖于 2 和 8 的状态，8 依赖于 2 和 6 的状态，6 依赖于 2 和 4 的状态，4 依赖于 2 和 2 的状态，可以找到一个递推关系。说明该题可能可以用动态规划来解决了。

这道题相比前面的几个题目，递推公式没有那么好推导出来了。需要思考一下。

首先，可以想 dp[i]最大乘积是怎么得到的呢？其实可以从1遍历 j，然后有两种渠道得到dp[i]：

• 一个是 j * (i - j) 直接相乘
• 一个是 j * dp[i - j]，相当于是继续拆分 (i - j)

比如 i = 6 拆成两个数时：

j=1，(i-j)=5
j=2，(i-j)=4
j=3，(i-j)=3
j=4，(i-j)=2
j=5，(i-j)=1

在这个情况 dp[i] = j * (i - j)

那拆成三个数及以上呢？脑子转得快的同学已经想到了，没错，就是 dp[i] = j * dp[i - j]，相当于对 i-j 进行进一步拆分。对这个拆分不理解的话，可以回想 dp 数组的定义。

// 1. 确定 dp[i] 含义：i 拆分后得到的最大的乘积
// 2. 确定递推公式：dp[i] = Math.max(dp[i], j * dp[i-j], j * (i - j));
// 3. 初始化 dp[2] = 1 因为最基本的 2 = 1 + 1 且 dp[0] 和 dp[1] 都没有意义
// 4. 确定遍历顺序
// 5. 打印 dp[]
const integerBreak = (n) => {
	let dp = new Array(n + 1).fill(0);
	dp[2] = 1;
	for (let i = 3; i <= n; i++) {
		// 根据前面分析 这里遍历到一半即可（优化点）
		// for (let j = 1; j < i; j++)
		for (let j = 1; j <= i / 2; j++) {
			dp[i] = Math.max(dp[i], j * dp[i-j], j * (i - j));
			// 为什么 dp[i] 也要？
			// 比如先固定了i=3 然后j去遍历去拆分这个3
			// 那在这个内循环过程其实会得到多次 dp[i]，所以也需要去 dp[i] 最大值
		}
	}
	return dp[n];
}
console.log(integerBreak(10)); // 36
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

四、不同的二叉搜索树（难点）

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

首先，先来了解一下什么是二叉搜索树。

二叉搜索树（Binary Search Tree，BST）是一种二叉树的特殊形式，它具有以下性质：

1. 对于二叉搜索树中的每个节点，其左子树中的所有节点的值小于该节点的值。
2. 对于二叉搜索树中的每个节点，其右子树中的所有节点的值大于该节点的值。
3. 左右子树也分别为二叉搜索树。

这个性质保证了二叉搜索树的有序性，使得在二叉搜索树中进行搜索、插入和删除操作具有较高的效率。由于其有序性质，二叉搜索树常用于实现一些基于有序数据的操作，例如搜索、插入、删除等。常见的应用包括集合、映射等数据结构的实现。

以下是一个二叉搜索树的示例：

      6
     / \
    4   8
   / \ / \
  2  5 7  9
1
2
3
4
5

先分析题目场景，当 n = 1：有1种

    1
1

n = 2：有2种

      2
     /
    1
    或者
      2
       \
        1
1
2
3
4
5
6
7

n = 3：有5种

      1
       \
        3
       /
     2
    或者
      1
       \
        2
          \
           3
	或者
      2
     /  \
    1   3
	或者
      3
     /
    2
   /
 1
	或者
      3
     /
    1
      \
       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

可以发现，n = 3 似乎跟 n = 1 和 n = 2 有一定关系：头节点为1 + 头节点为2 + 头节点为3的情况之和。

对于头节点为1时，有：左子树0节点 * 右子树2节点。

对于头节点为2时，有：左子树1节点 * 右子树1节点。

对于头节点为3时，有：左子树2节点 * 右子树0节点。

可以进一步发现，左子树0节点的情况就是 n = 0 的情况；右子树2节点就是 n=2；左子树1节点和右子树1节点都是 n=1；左子树2节点就是 n=2；右子树0节点就是 n=0。

得到递推公式：dp[3] = (dp[0] * dp[2]) + (dp[1] * dp[1]) + (dp[2] + dp[0])。

进一步分析，我们回到 dp[i]，也就是会等于 头节点为1的情况+头节点为2的情况+头节点为3的情况+头节点为4…

也就是要枚举所有以j为头节点的情况，那如果以 j 为头节点，它的左子树将会有 j-1 个节点（因为二叉搜索树，比它小的都会在左边），它的右子树将会有 i-j 个。即有 dp[i] * dp[i-j] 种（左右子树相乘）。

最后得到 dp[i] += dp[j-1] * dp[i-j]。因为遍历j时是从1~i，需要求和，即当头节点为1，头节点为2，头节点为…，才是得到所有场景。

// 1. 确认 dp[i] 含义：当为i，有 dp[i] 种不同的二叉树
// 2. 确认递推公式：
// 3. 状态初始化
// 4. 确认循环顺序
// 5. 打印 dp[]
const numTrees = (n) => {
	let dp = new Array(n+1).fill(0);
	dp[0] = 1;
	dp[1] = 1;
	for(let i = 2; i <= n; i++) {
		for(let j = 1; j <= i; j++) {
			// 遍历不同的 j 需要把所有头节点的情况加起来
			dp[i] += dp[j-1] * dp[i-j];
		}
	}
	return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17