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

62.不同路径

题目链接：https://leetcode.cn/problems/unique-paths/
文档讲解：https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE…
视频讲解：https://www.bilibili.com/video/BV1ve4y1x7Eu/

思路

• 确定dp数组以及下标的含义：走到第i行第j个格子有dp[i][j]种方法。
• 确定递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1];因为可以往下走和往右走，所以第i行第j列的点要么是从左边来，要么是从上面来，所以是把这两个格子的方法数相加。
• dp数组如何初始化：初始化第一行和第一列的数据，都只有一种方法可以到达，就是一直往右走或一直往下走。
• 确定遍历顺序：dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
• 打印dp数组，用于debug。

代码

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 i = 0; i < n; i++) dp[0][i] = 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];
    }
}

分析：时间复杂度：O(m * n)，空间复杂度：O(m * n)。

63. 不同路径 II

题目链接：https://leetcode.cn/problems/unique-paths-ii/
文档讲解：https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE…
视频讲解：https://www.bilibili.com/video/BV1Ld4y1k7c6/

思路

• 确定dp数组以及下标的含义：走到第i行第j个格子有dp[i][j]种方法。
• 确定递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1];因为可以往下走和往右走，所以第i行第j列的点要么是从左边来，要么是从上面来，所以是把这两个格子的方法数相加。但如果这一格有障碍，就为0。
• dp数组如何初始化：本题和上面一道题不以言大哥地方在于本体有障碍，那么初始化的时候，如果遇到了障碍，后面的格子就不可达，为0。
• 确定遍历顺序：dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
• 打印dp数组，用于debug。

代码

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) dp[0][i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

分析：时间复杂度：O()，空间复杂度：O()。

343. 整数拆分

题目链接：https://leetcode.cn/problems/integer-break/
文档讲解：https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
视频讲解：https://www.bilibili.com/video/BV1Mg411q7YJ/

思路

• 确定dp数组以及下标的含义：分拆数字i，可以得到的最大乘积为dp[i]。
• 确定递推公式：从1遍历j，然后有两种渠道得到dp[i]：
  • 一个是j * (i - j) 直接相乘。
  • 一个是j * dp[i - j]，相当于是拆分(i – j)。
  • 最后递推公式为dp[i] = Math.max(j * (i - j), Math.max(j * dp[i - j], dp[i]));
  • 在j循环的过程中，会多次计算dp[i]，取最大的。
• dp数组如何初始化：dp[0]和dp[1]其实是没有意义的，就初始化为0。

dp[0] = 0;
dp[1] = 0;
dp[2] = 1;

• 确定遍历顺序：从前向后遍历。
• 打印dp数组，用于debug

代码

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) { // 要拆分成近似相等的数，j大于i的情况就不考虑了
                dp[i] = Math.max(j * (i - j), Math.max(j * dp[i - j], dp[i]));
            }
        }
        return dp[n];
    }
}

分析：时间复杂度：O(n²)，空间复杂度：O(n)。

96.不同的二叉搜索树

题目链接：https://leetcode.cn/problems/unique-binary-search-trees/
文档讲解：https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7…
视频讲解：https://www.bilibili.com/video/BV1eK411o7QA/

思路

• 确定dp数组以及下标的含义：有i个节点的二叉搜索树有dp[i]中不同的形状。
• 确定递推公式：确定一个根节点后，这个二叉树的形状数由左右子树形状数量相乘决定，即dp[i] += dp[j] * dp[i - j - 1];。
• dp数组如何初始化：dp[0] = 1; dp[1] = 1;，0个节点也算一种形状。
• 确定遍历顺序：从前往后遍历。
• 打印dp数组，用于debug

代码

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}

分析：时间复杂度：O(n²)，空间复杂度：O(n)。