62.不同路径
题目链接：62.不同路径
文档讲解：代码随想录
状态：还行
思路：当前状态的只有可能是从上面或者左边过来的，所以 dp[i][j] = dp[i-1] + dp[j-1]
题解：
public int uniquePaths(int m, int n) {
if (m == 1 && n == 1) {
return 1;
}
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
63. 不同路径 II
题目链接：63. 不同路径 II
文档讲解：代码随想录
状态：还行
思路：
对于第一行中的元素（不包括第一个元素），路径数量只取决于左边格子的路径数量。
对于第一列中的元素（不包括第一个元素），路径数量只取决于上边格子的路径数量。
对于其他位置，路径数量为上边和左边格子的路径数量之和。
如果当前位置有障碍物，则将该位置的路径数量设为0。
题解：
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 如果起点本身有障碍物，返回 0，因为无法出发
if (obstacleGrid[0][0] == 1) {
return 0;
}
int m = obstacleGrid.length; // 获取网格的行数
int n = obstacleGrid[0].length; // 获取网格的列数
int[][] dp = new int[m][n]; // 创建一个二维数组 dp 用于存储每个位置的路径数量
dp[0][0] = 1; // 起点位置的路径数量设为 1
// 遍历网格
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果在第一行，且不是第一个元素
if (i == 0 && j > 0) {
dp[i][j] = dp[i][j - 1]; // 只能从左边的格子过来
}
// 如果在第一列，且不是第一个元素
if (j == 0 && i > 0) {
dp[i][j] = dp[i - 1][j]; // 只能从上边的格子过来
}
// 对于其他位置
if (i > 0 && j > 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 路径数量为从上边和左边格子的路径数量之和
}
// 如果当前格子有障碍物，路径数量为 0
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
}
}
}
// 返回终点位置的路径数量
return dp[m - 1][n - 1];
}
343.整数拆分
题目链接：343.整数拆分
文档讲解：代码随想录
状态：不会
思路：
dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。从1遍历j，然后有两种渠道得到dp[i]
第一种是j * (i - j) 直接相乘。
第二种是j * dp[i - j]。这里的dp[i-j] 表示将 i-j 进一步拆分后得到的最大乘积，这个拆分过程中有递归的影子，所以第二种方式就是一堆数字相乘最后能得到的最大值。
题解：
public int integerBreak(int n) {
// dp[i] 表示将正整数 i 拆分成至少两个正整数的和后，这些正整数的乘积的最大值。
int[] dp = new int[n + 1];
dp[2] = 1;
/*遍历计算：从 i=3 开始遍历到 i=10，对每个 i 进行如下计算：
当 i=3 时，j 可以取 1 或 2，分别计算 j*(3-j) 和 j*dp[3-j]，取最大值，得到 dp[3] = 2。
当 i=4 时，j 可以取 1、2 或 3，分别计算 j*(4-j) 和 j*dp[4-j]，取最大值，得到 dp[4] = 4。
当 i=5 时，j 可以取 1、2、3 或 4，分别计算 j*(5-j) 和 j*dp[5-j]，取最大值，得到 dp[5] = 6。
当 i=6 时，j 可以取 1、2、3、4 或 5，分别计算 j*(6-j) 和 j*dp[6-j]，取最大值，得到 dp[6] = 9。
当 i=7 时，j 可以取 1、2、3、4、5 或 6，分别计算 j*(7-j) 和 j*dp[7-j]，取最大值，得到 dp[7] = 12。
当 i=8 时，j 可以取 1、2、3、4、5、6 或 7，分别计算 j*(8-j) 和 j*dp[8-j]，取最大值，得到 dp[8] = 18。
当 i=9 时，j 可以取 1、2、3、4、5、6、7 或 8，分别计算 j*(9-j) 和 j*dp[9-j]，取最大值，得到 dp[9] = 27。
当 i=10 时，j 可以取 1、2、3、4、5、6、7、8 或 9，分别计算 j*(10-j) 和 j*dp[10-j]，取最大值，得到 dp[10] = 36。*/
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= i - j; j++) {
// max(j * (i-j), j * dp[i-j])：这部分是关键，它考虑了两种情况：
// j * (i-j)：将整数 i 拆分为两个数，即 j 和 i-j，它们的乘积为 j * (i-j)。
// j * dp[i-j]：将整数 i 拆分成 j 和若干个数之和，其中至少一个数大于 1。dp[i-j] 表示将 i-j 进一步拆分后得到的最大乘积，因此乘积为 j * dp[i-j]。
// max(dp[i], ...)：这部分确保我们每次更新 dp[i] 时，取最大的乘积。
// 因为我们要求的是整体的最大乘积，所以要比较当前计算出的乘积与之前已经计算过的 dp[i] 的值，取其中较大的那个作为 dp[i] 的值。也就是j取不同值时算到的各个dp[i]中取最大的
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
96.不同的二叉搜索树（可跳过）
题目链接：96.不同的二叉搜索树
文档讲解：代码随想录
状态：不会
数学思路：
卡特兰数的简单应用，递推通项公式都可以简单求解。
通项公式：
f
(
n
)
=
1
n
+
1
C
2
n
n
f(n) = \frac{1}{n+1} C_{2n}^{n}
f(n)=n+11C2nn
递推公式： f ( n ) = ∑ k = 1 n f ( n − k ) f ( k − 1 ) = ( 2 n ) ! ( n + 1 ) ! n ! f(n) = \sum_{k=1}^{n} f(n-k) f(k-1) = \frac{(2n)!}{(n+1)!n!} f(n)=∑k=1nf(n−k)f(k−1)=(n+1)!n!(2n)!
通过这道题可以非常简单的得到递推公式：
- 选数字k作为二叉排序树的根节点
- 小于k的数字(1, 2, …, k-1)构成左子树，左子树一共有 f ( k − 1 ) f(k-1) f(k−1) 种可能
- 大于k的数字 (k+1, …, n)构成右子树，右子树一共有 f ( n − k ) f(n-k) f(n−k)种可能
- 选k作为根节点一共有 f ( n − k ) f ( k − 1 ) f(n-k) f(k-1) f(n−k)f(k−1) 种可能
- 一共有n个数字可以作为根节点，故一共 f ( n ) = ∑ k = 1 n f ( n − k ) f ( k − 1 ) f(n) = \sum_{k=1}^{n} f(n-k) f(k-1) f(n)=∑k=1nf(n−k)f(k−1)种可能
dp思路：
- 目标：计算节点数量为 i 时的二叉搜索树数量 dp[i]。
- 遍历根节点：对于每个可能的根节点值 j，其中 j 的取值范围是从 1 到 i。这表示我们考虑将每个节点作为根节点，来构建二叉搜索树。
- 左子树和右子树：当我们选择节点 j 作为根节点时，左子树包含节点值从 1 到 j-1 的所有节点，右子树包含节点值从 j+1 到 i 的所有节点。
- 状态转移：对于每个根节点 j，其左子树的节点数量为 j-1，右子树的节点数量为 i-j。因此，以节点 j 为根的二叉搜索树数量为 dp[j - 1] * dp[i - j]。
- 累加更新：将所有可能的以节点 j 为根的二叉搜索树数量累加到 dp[i] 上，即 dp[i] += dp[j - 1] * dp[i - j];。这样可以计算出节点数量为 i 时的所有可能的二叉搜索树数量。
- 结果：最终，dp[i] 的值即为节点数量为 i 时的二叉搜索树数量。
数学题解：
//数学方法
public int numTrees(int n) {
// 计算组合数 C(2n, n)
long C = binomialCoeff(2 * n, n);
// 返回 Catalan 数 C_n = C / (n + 1)
return (int) (C / (n + 1));
}
// 计算二项式系数 C(n, k)
private long binomialCoeff(int n, int k) {
long res = 1;
// C(n, k) = C(n, n - k), 提高效率
if (k > n - k) {
k = n - k;
}
// 计算 C(n, k)
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
dp题解：
public int numTrees(int n) {
// 创建一个数组用于存储不同节点数量对应的二叉搜索树数量
int[] dp = new int[n + 1];
// 初始化，当节点数量为 0 或 1 时，只有一种情况，即空树或只有一个节点的树
dp[0] = 1;
dp[1] = 1;
// 计算不同节点数量对应的二叉搜索树数量
// 变量 i 表示当前正在计算的节点数量
for (int i = 2; i <= n; i++) {
// 变量 j 表示当前正在考虑作为根节点的值,
// 因为是BST,左子树包含了从 1 到 j-1 的节点，右子树包含了从 j+1 到 i 的节点
for (int j = 1; j <= i; j++) {//头结点从1开始遍历,遍历到结点i
// 将每个数作为根节点，计算其左右子树的 BST 数量，
// 然后将左右子树的数量相乘，累加得到以当前数为根节点的 BST 数量
// 但是为了求当前i节点为根节点的数量,还要把2到i的节点数量加起来
dp[i] += dp[j - 1] * dp[i - j];
}
}
// 返回 n 个节点的 BST 数量
return dp[n];
}
