62.不同路径

链接：. - 力扣（LeetCode）

题目描述：

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

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

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

示例 1：

输入：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

 思路

1. 确定dp数组（dp table）以及下标的含义，因为题目是一个矩阵，因此我们需要定义一个二维的dp数组来记录每个方格的状态，dp数组的含义应该是从dp[0][0]位置走到dp[n][m]位置总共有多少种方法
2. 确定递推公式，因此我们机器人行走只能由上往下走或者由左往右走，因此我们位置的上一个格子应该为dp[n-1][m]，目标位置的左边的格子应该为dp[n][m-1]，因此，我们就可以知道要达到我们的目标位置的方法为dp[n][m] = dp[n-1][m] + dp[n][m-1]
3. dp数组如何初始化，根据我们的递推公式，我们可知我们的状态都是由上面和左面的方格推导得出的，因此我们需要初始化最上面的格子和最左面的格子，因此就可以知道dp[0][i]为1，并且dp[i][0]也为1，因为只能向下走或者向右走，因此到达同一行右边的所有格子只有一种方法，同理到达同一列下的所有格子也只有一种方法
4. 确定遍历顺序，根据推导公式就可知，我们应该由上往下遍历，由左往右遍历
5. 举例推导dp数组，查找debug

代码

int uniquePaths(int m, int n) {int dp[m][n];for(int i = 0; i < m ; i++)dp[i][0] = 1;for(int j = 0; j < n ; j++)dp[0][j] = 1;for(int i = 1; i < m ; i++){for(int j = 1; j < n ;j++)dp[i][j] = dp[i-1][j] + dp[i][j-1];}return dp[m-1][n-1];
}

63.不同路径II

链接：. - 力扣（LeetCode）

题目描述：

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

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

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

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

示例 1：

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

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

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

思路

1. 确定dp数组（dp table）以及下标的含义为，题目是一个矩阵，因此我们需要定义一个二维的dp数组来记录每个方格的状态，dp数组的含义应该是从dp[0][0]位置走到dp[n][m]位置总共有多少种方法
2. 确定递推公式，因此我们机器人行走只能由上往下走或者由左往右走，因此我们位置的上一个格子应该为dp[n-1][m]，目标位置的左边的格子应该为dp[n][m-1]，因此，我们就可以知道要达到我们的目标位置的方法为dp[n][m] = dp[n-1][m] + dp[n][m-1]，因为本题中设置了障碍，因此我们在遇到障碍时不能继续行走，因此需要加上一个判断条件判断是否有障碍
3. dp数组如何初始化，在本题中，根据我们的递推公式，我们可知我们的状态都是由上面和左面的方格推导得出的，因此我们需要初始化最上面的格子和最左面的格子，但是注意，如果出现了障碍，则代表我们走不到后面的位置，因此本题的初始化与上题不同，需要加上判断
4. 确定遍历顺序，根据推导公式就可知，我们应该由上往下遍历，由左往右遍历
5. 举例推导dp数组

代码

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) {int m = obstacleGridSize;int n = *obstacleGridColSize;// 如果起点或终点有障碍物，直接返回0if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)return 0;int dp[m][n];memset(dp, 0, sizeof(dp)); // 初始化为0// 处理边界条件dp[0][0] = 1; // 起点for(int i = 1; i < m; i++) {if(obstacleGrid[i][0] == 0)dp[i][0] = dp[i-1][0];}for(int j = 1; j < n; j++) {if(obstacleGrid[0][j] == 0)dp[0][j] = dp[0][j-1];}// 计算路径数量for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {if(obstacleGrid[i][j] == 0)dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];
}

343.整数拆分

链接：. - 力扣（LeetCode）

题目描述：

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

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

示例 2:

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

提示:

• 2 <= n <= 58

 思路

• 确定dp数组及下标含义：

  • 我们可以使用一个一维数组 dp，其中 dp[i] 表示正整数 i 拆分后可以获得的最大乘积。

• 确定递推公式：

  • 当考虑拆分正整数 i 时，我们可以考虑将其拆分成两个正整数 j 和 i-j，其中 1 <= j < i。这样，i 的拆分乘积可以表示为 j * (i-j)。
  • 但是，j * (i-j) 并不一定是最优的，因为 j 和 (i-j) 可能还可以继续拆分，因此我们需要比较 dp[j] * dp[i-j] 和 j * (i-j)，选择其中的最大值作为 dp[i] 的值。
  • 因此，递推公式为：dp[i] = max(dp[j] * dp[i-j], j * (i-j))，其中 1 <= j < i。

• dp数组初始化：

  • dp[0] 和 dp[1] 都是0，因为它们都无法拆分成两个正整数的和。
  • dp[2] 为1，因为2只能拆分成1+1，乘积为1。
  • dp[3] 为2，因为3可以拆分成1+2，乘积为2。
  • 依次类推，初始化数组中的值。

• 确定遍历顺序：

  • 我们需要先计算较小的正整数的最大乘积，然后依次向上计算较大的正整数的最大乘积，直到计算出目标正整数 n 的最大乘积。

• 举例推导dp数组

代码

int max(int a, int b) {return (a > b) ? a : b;
}int integerBreak(int n) {// dp[i] 为正整数 i 拆分后的结果的最大乘积int dp[n + 1];dp[2] = 1;for (int i = 3; i <= n; i++) {dp[i] = 0;for (int j = 1; j <= i - j; j++) {// 这里的 j 其实最大值为 i-j,再大只不过是重复而已，// 并且，在本题中，我们分析 dp[0], dp[1] 都是无意义的，// j 最大到 i-j, 就不会用到 dp[0] 与 dp[1]dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));// j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘// 而 j * dp[i - j] 是将 i 拆分成两个以及两个以上的个数,再相乘。}}return dp[n];
}

96.不同的二叉搜索树

链接：. - 力扣（LeetCode）

题目描述：

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

思路

由图可以知道，n为3的情况可以由n为2和n为1的情况推导出来

头节点为1 = 左子树0个节点 * 右子树2个节点

头节点为2 = 左子树1个节点 * 左子树1个节点

头节点为3 = 左子树2个节点 * 右子树0个节点

dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2]*dp[0]

1. 确定dp数组（dp table）以及下标的含义，dp[i]为i值有dp[i]种二叉搜索树
2. 确定递推公式，dp[i] += dp[j-1] * dp[i-j]，j代表左子树的情况
3. dp数组如何初始化，dp[0]代表空二叉树，也满足条件，因此值应该为1
4. 确定遍历顺序，根据递推公式，可知由小往大去遍历
5. 举例推导dp数组

代码

int numTrees(int n) {int dp[n+1];memset(dp, 0, sizeof(dp));dp[0] = 1;for(int i = 1; i <= n ; i++){for(int j = 1; j <= i ; j++)dp[i] += dp[j-1] * dp[i-j];}return dp[n];
}