算法训练（leetcode）二刷第二十九天 | 62. 不同路径、63. 不同路径 II、343. 整数拆分、96. 不同的二叉搜索树

62. 不同路径

leetcode题目地址

二维数组

动态规划。题目中说明只能向下或向右移动，因此每个位置的更新只与左侧和上侧位置的状态有关。

• 确认dp数组含义：dp[i][j]表示到达[i, j]位置的路径数
• 递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 初始化：起始状态一直向右走或一直向下走，均算为一条路径。因此dp[i][0]和dp[0][j]均赋值为1。
• 遍历顺序：每个位置dp[i][j]更新只与dp[i-1][j]和dp[i][j-1]有关，因此从左向右，从上到下遍历。

时间复杂度： $O(n\ast m)$
空间复杂度： $O(n\ast m)$

// java
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];
        
    }
}

滚动数组

时间复杂度： $O(n\ast m)$
空间复杂度： $O(n)$

// java
class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        for(int j=0; j<n; j++){
            dp[j] = 1;
        }

        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }
}

63. 不同路径 II

leetcode题目地址

二维数组

与上题思路相同，只是多了障碍。初始化时遇到障碍则停止初始化，障碍后面的位置不可达。在动态规划迭代过程中，若当前位置有障碍则直接跳过。

时间复杂度： $O(n\ast m)$
空间复杂度： $O(n\ast m)$

// java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;

        int[][] dp = new int[m][n];

        for(int i=0; i<m && obstacleGrid[i][0] == 0; i++){
            dp[i][0] = 1;
        }
    
        for(int j=0; j<n && obstacleGrid[0][j] == 0; j++){
            dp[0][j] = 1;
        }

        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(obstacleGrid[i][j] == 1) continue;
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];

    }
}

滚动数组

这里需要注意的是j是从0开始的，因为每一列的第一个元素可能会出现障碍，而在滚动数组中，障碍位置的dp[i]=0，因此需要从0开始，防止漏掉更新每行第一个位置的状态。

时间复杂度： $O(n\ast m)$
空间复杂度： $O(n)$

// java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;

        int[] dp = new int[n];

        for(int j=0; j<n && obstacleGrid[0][j] == 0; j++) dp[j] = 1;

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

343. 整数拆分

leetcode题目地址

动态规划

对1-n的每一个数进行拆分，后面的拆分结果基于前面的拆分结果。对每个数i从1到i-1进行拆分，找出其最大拆分值。

• 确认dp数组含义：dp[i]表示i拆分后的最大乘积
• 递推公式：dp[i] = max(dp[i], j*(i-j), j*dp[i-j])，j表示i拆分出来的一个数，i-j是剩余部分，dp[i-j]是对i-j继续拆分，这一拆分基于前面的结果。
• 初始化：0和1无法拆分，均赋值0；2拆分后最大为1。
• 遍历顺序：从3开始一直遍历到n。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 0;
        dp[2] = 1;
        for(int i=3; i<=n; i++){
            for(int j=1; j<i; j++){
                dp[i] = Math.max(Math.max(dp[i], j*(i-j)), j*dp[i-j]);
            }
        }
        return dp[n];
    }
}

数论方法

尽可能多的拆3，最终求得的就是最大拆分。
**Tips：**当剩余4时则不再继续拆分，若对4再拆则最终结果不再是最大拆分。

// java
class Solution {
    public int integerBreak(int n) {
        if(n<=3) return n-1;
        int k = (n-4)/3, res = 1;
        while(n-3>1) {
            res *= 3;
            n -= 3;
        }
        res *= n;
        return res;
    }
}

96. 不同的二叉搜索树

leetcode题目地址

动态规划

dp[i]存储i个结点的不同二叉树结构数。可以将一颗二叉搜索树分为三个部分：头结点、左子树、右子树。

对i个节点构成的二叉搜索树，搜索汇总其中的每一个节点j作头结点的情况，则，共有j-1个结点构成左子树，i-j个结点构成右子树。

因此，共i个结点，j作为头结点构成的二叉搜索树有dp[j-1] * dp[i-j]种情况，即左子树的二叉搜索树不同组合个数乘以右子树的二叉搜索树不同组合个数。

因此，得到递推公式：dp[i] += dp[j-1] * dp[i-j];

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {
    public int numTrees(int n) {

        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i=1; i<=n; i++){
            // j作为头结点的情况
            for(int j=1; j<=i; j++){
                // dp[j-1]：左子树 dp[i-j]：右子树
                dp[i] += dp[j-1] * dp[i-j];
            }
        } 
        return dp[n];
        
    }
}

数论方法

n个元素组成的不同序列个数为：
$$\frac{1}{n+1}{C}_{2n}$$

**Tips:**在计算过程中，要乘除同时进行，否则会溢出。记录结果要用long，用int在计算过程中会溢出，在返回结果时转换类型即可。

// java
class Solution {
    public int numTrees(int n) {
        int denominator = n, cnt = n;
        int numerator = 2*n;
        long result = 1, res = n+1;
        while(cnt>0){
            result *= numerator;
            numerator--;
            if(result % cnt == 0) result /= cnt;
            else res *= cnt;
            cnt--;
        }
        result /= res;
        return (int)result;
    }
}