leetcode打卡#day42 62. 不同路径、63. 不同路径 II、343. 整数拆分、96. 不同的二叉搜索树

62. 不同路径

class Solution {
public:
    //动态规划
    int uniquePaths(int m, int n) {
        //dp数组，记录到达目的地的路径数
        vector<vector> dp(m, vector(n, 0));
        //初始化
        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][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];

    }
};

63. 不同路径 II

class Solution {
//动态规划， 此时有障碍的情况 
public:
    int uniquePathsWithObstacles(vector<vector>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        //记录到达目的地的不同路径数
        vector<vector> dp(m, vector(n, 0));
        //初始化
        for(int i=0; i < m && !obstacleGrid[i][0]; i++) dp[i][0] = 1;
        for(int i=0; i < n && !obstacleGrid[0][i]; i++) dp[0][i] = 1;
        //遍历
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(!obstacleGrid[i][j]) dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

343. 整数拆分

class Solution {
public:
    //动态规划 -- dp[i]的含义： 乘积最大的该整数n的拆分
    int integerBreak(int n) {
        vector dp(n+1, 0);
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i-1; j++){
                dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

96. 不同的二叉搜索树

class Solution {
public:
    //动态规划问题: vector dp[i]记录 i 个结点有多少种二叉搜索树
    int numTrees(int n) {
        vector dp(n+1, 0);
        //初始化
        dp[0] = 1;
        //遍历
        for (int i = 1; i <= n; i++){
            //dp[i] = 左子树个数 * 右子树的个数
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];

    }
};