代码随想录day29：动态规划part2

62. 不同路径

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[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];}
}

也可以路径压缩，一维数组压缩到常量，二维数组压缩到一维

for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[j] += dp[j - 1]; // dp[j] = dp[j] (正上方) + dp[j - 1] (正左方)}
}外层循环遍历行 i，从第二行开始。
内层循环遍历列 j，从第二列开始。
对于每个位置 (i, j)，更新 dp[j]：
dp[j] 代表到达当前列的路径数。
dp[j - 1] 是到达左边单元格的路径数。
通过 dp[j] += dp[j - 1]，我们将上方的路径数（dp[j]）和左方的路径数（dp[j - 1]）相加，得到新的路径数。

63. 不同路径 II

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];// 初始化第一列for (int i = 0; i < m; i++) {if (obstacleGrid[i][0] == 1) {dp[i][0] = 0;// 之后的所有行都应该是 0break; } else {dp[i][0] = 1;}}// 初始化第一行for (int j = 0; j < n; j++) {if (obstacleGrid[0][j] == 1) {dp[0][j] = 0;// 之后的所有列都应该是 0break; } else {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];if(obstacleGrid[i][j] == 1) dp[i][j] = 0;}}return dp[m - 1][n - 1];}
}

自己写的时候写错了第一行的初始化，

for(int i = 0; i < m; i++){if(obstacleGrid[i][0] == 1) {dp[i][0] = 0;} else {dp[i][0] = 1;}
}

没考虑到一个问题，如果第一列的某个单元格是障碍物（1），那么该行之后的所有单元格都应该是 0，因为无法通过障碍物。

所以需要在遇到障碍物后，停止设置后续单元格的值为 1。如最终代码那样写。

343. 整数拆分

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

nmmd，很难

96. 不同的二叉搜索树

class Solution {Map<Integer, Integer> map = new HashMap<>();public int numTrees(int n) {if(n == 0 || n == 1) return 1;if(map.containsKey(n)) return map.get(n);int res = 0;for(int i = 1; i <= n; i++){int left = numTrees(i - 1);int right = numTrees(n - i);res += left * right;}map.put(n,res);return res;}
}

递归构造的性质

在 numTrees(n) 的实现中，节点的选择和拆分方式确保了生成的树都是 BST。以下是如何保证这一点的详细分析：

根节点的选择:
- 在函数中，我们遍历所有可能的根节点 i，从 1 到 n。选择 i 作为根节点意味着：
  - 所有小于 i 的节点（1 到 i-1）将会在左子树中。
  - 所有大于 i 的节点（i+1 到 n）将会在右子树中。
递归构造左子树和右子树:
- 对于左子树，我们递归调用 numTrees(i - 1)，计算左侧所有节点的组合。
- 对于右子树，我们递归调用 numTrees(n - i)，计算右侧所有节点的组合。
- 这种递归方式保证了左子树和右子树的节点始终遵循 BST 的性质。
使用 Map 来存储已经计算过的结果，避免了重复计算。