当前位置：首页 > article >正文

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

article 2024/10/10 22:14:02

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;
                // 之后的所有行都应该是 0
                break; 
            } else {
                dp[i][0] = 1;
            }
        }

        // 初始化第一行
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                dp[0][j] = 0;
                // 之后的所有列都应该是 0
                break; 
            } 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 来存储已经计算过的结果，避免了重复计算。