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
思路
- 确定dp数组（dp table）以及下标的含义，因为题目是一个矩阵，因此我们需要定义一个二维的dp数组来记录每个方格的状态，dp数组的含义应该是从dp[0][0]位置走到dp[n][m]位置总共有多少种方法
- 确定递推公式，因此我们机器人行走只能由上往下走或者由左往右走，因此我们位置的上一个格子应该为dp[n-1][m]，目标位置的左边的格子应该为dp[n][m-1]，因此，我们就可以知道要达到我们的目标位置的方法为dp[n][m] = dp[n-1][m] + dp[n][m-1]
- dp数组如何初始化，根据我们的递推公式，我们可知我们的状态都是由上面和左面的方格推导得出的，因此我们需要初始化最上面的格子和最左面的格子，因此就可以知道dp[0][i]为1，并且dp[i][0]也为1，因为只能向下走或者向右走，因此到达同一行右边的所有格子只有一种方法，同理到达同一列下的所有格子也只有一种方法
- 确定遍历顺序，根据推导公式就可知，我们应该由上往下遍历，由左往右遍历
- 举例推导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.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]为0或1
思路
- 确定dp数组（dp table）以及下标的含义为，题目是一个矩阵，因此我们需要定义一个二维的dp数组来记录每个方格的状态，dp数组的含义应该是从dp[0][0]位置走到dp[n][m]位置总共有多少种方法
- 确定递推公式，因此我们机器人行走只能由上往下走或者由左往右走，因此我们位置的上一个格子应该为dp[n-1][m]，目标位置的左边的格子应该为dp[n][m-1]，因此，我们就可以知道要达到我们的目标位置的方法为dp[n][m] = dp[n-1][m] + dp[n][m-1]，因为本题中设置了障碍，因此我们在遇到障碍时不能继续行走，因此需要加上一个判断条件判断是否有障碍
- dp数组如何初始化，在本题中，根据我们的递推公式，我们可知我们的状态都是由上面和左面的方格推导得出的，因此我们需要初始化最上面的格子和最左面的格子，但是注意，如果出现了障碍，则代表我们走不到后面的位置，因此本题的初始化与上题不同，需要加上判断
- 确定遍历顺序，根据推导公式就可知，我们应该由上往下遍历，由左往右遍历
- 举例推导dp数组
代码
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) {
int m = obstacleGridSize;
int n = *obstacleGridColSize;
// 如果起点或终点有障碍物，直接返回0
if(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]
- 确定dp数组（dp table）以及下标的含义，dp[i]为i值有dp[i]种二叉搜索树
- 确定递推公式，dp[i] += dp[j-1] * dp[i-j]，j代表左子树的情况
- dp数组如何初始化，dp[0]代表空二叉树，也满足条件，因此值应该为1
- 确定遍历顺序，根据递推公式，可知由小往大去遍历
- 举例推导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];
}
