代码随想录算法训练营第三十三天-62不同路径、63不同路径 II、343 整数拆分、96不同的二叉搜索树

前言
状态：62AC、63AC、343 不会。96 一刷先跳过。
更新

1	24-06-19 初始记录

初步题解

62 不同路径

题目链接：(https://leetcode.cn/problems/unique-paths)

确定 dp[m][n] 的含义：网格大小为 m x n 时的路径数
递推公式：dp[m][n] = dp[m][n-1] + dp[m-1][n]
dp 数组的初始化：所有纵列横列为 1 的，都是 1。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public static int uniquePaths(int m, int n) {  
    int[][] dp = new int[m + 1][n + 1];  
  
    if (m <= 1 || n <= 1) {  
        return 1;  
    }  
  
  
    for (int i = 1; i <= m; i++) {  
        for (int j = 1; j <= n; j++) {  
            if (i == 1 || j == 1) {  
                dp[i][j] = 1;  
                continue;  
            }  
  
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  
        }  
    }  
      
    return dp[m][n];  
}

63 不同路径 II

题目链接：(https://leetcode.cn/problems/unique-paths-ii)

这题的五部曲分析应该和上题一样。多了障碍格子，遇到障碍格子时，数计 0 （注意一下边界问题就行）。

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++) {  
        for (int j = 0; j < n; j++) {  
            if (obstacleGrid[i][j] == 1) {  
                dp[i][j] = 0;  
                continue;  
            }  
  
            if (i == 0 && j == 0) {  
              dp[i][j] = 1;  
            } else if (i == 0) {  
                dp[i][j] = dp[i][j - 1];  
            } else if (j == 0) {  
                dp[i][j] = dp[i - 1][j];  
            } else {  
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  
            }  
        }  
    }  
  
    // System.out.println("dp = " + Arrays.deepToString(dp));  
  
    return dp[m - 1][n - 1];  
}

343 整数拆分

题目链接：(https://leetcode.cn/problems/integer-break/)

确定 dp[i] 的含义：正整数 i 的拆分最大化乘积。
递推公式：想不出来。🤕
dp 数组的初始化：dp[2] = 1。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

96 不同的二叉搜索树

题目链接：(https://leetcode.cn/problems/unique-binary-search-trees)

看解析

62 不同路径

解析：(https://programmercarl.com/0062.不同路径.html)

有一个状态压缩版本：

class Solution {
    public int uniquePaths(int m, int n) {
        // 在二维dp数组中，当前值的计算只依赖正上方和正左方，因此可以压缩成一维数组。
        int[] dp = new int[n];
        // 初始化，第一行只能从正左方跳过来，所以只有一条路径。
        Arrays.fill(dp, 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] (正左方)
            }
        }
        return dp[n - 1];
    }
}

63 不同路径 II

解析：(https://programmercarl.com/0063.不同路径II.html)

343 整数拆分

解析：(https://programmercarl.com/0343.整数拆分.html)

不是很懂，一刷先跳过了。

public static int integerBreak(int n) {  
    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];  
}

本题也可以用贪心，每次拆成 n 个 3，如果剩下是 4，则保留 4，然后相乘，但是这个结论需要数学证明其合理性！ 🥴本来想这么写的，但是好像想错了。具体的数学推导：(https://leetcode.cn/problems/integer-break/solutions/29098/343-zheng-shu-chai-fen-tan-xin-by-jyd/)

96 不同的二叉搜索树

解析：(https://programmercarl.com/0096.不同的二叉搜索树.html)