代码随想录算法训练营第二十九天| 62.不同路径, 63. 不同路径 II, 96.不同的二叉搜索树

今天是动态规划学习的第二天，接触了一些二维dp的题目。也有一些收获和总结。

 62.不同路径

题目链接：62. 不同路径 - 力扣（LeetCode）

这个题目是有一个mxn的地图，一个机器人从（0,0）走到（m-1,n-1）,问有多少种不同的路径。机器人每一次只能向下或向右走一格。首先我们dp[i][j]的含义是走到i，j坐标的方法数；由于只能向下或向右走，所以dp[i][j]=dp[i-1][j]+dp[i][j-1],这就是我们的递推公式；对于初始化，需要把第一行和第一列进行初始化，都初始化为1，因为只能一直向下或一直向右走；遍历顺序就是从左上到右下，手动递推一下也是没有问题的。具体代码实现如下所示：
 

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m+10][n+10];
        dp[0][0]=1;
        for(int i=1;i<m;i++) dp[i][0]=1;
        for(int j=1;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];
    }
};

63. 不同路径 II

题目链接：63. 不同路径 II - 力扣（LeetCode）

区别在于这个题目出现了障碍物，所以我们的dp过程出现了差别。dp数组的含义还是不变的，首先对于递推公式，如果dp[i][j]坐标下对应的是一个障碍，那么把dp[i][j]设置为0，不是障碍就可以按照我们之前的递推公式进行推导；对于初始化过程，同样是初始化第一行和第一列，将出现障碍前的位置都设置为1，障碍后的位置都初始化为0.具体代码实现如下所示：
 

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        int dp[m+10][n+10];
        bool isnnoreach=0;
        for(int i=0;i<m;i++) 
        {
            if(isnnoreach==1) dp[i][0]=0;
            else if(obstacleGrid[i][0]==0) dp[i][0]=1;
            else 
            {
               isnnoreach=1;
               dp[i][0]=0;
            }
        }
        isnnoreach=0;
        for(int j=0;j<n;j++)
        {
            if(isnnoreach==1) dp[0][j]=0;
            else if(obstacleGrid[0][j]==0) dp[0][j]=1;
             else 
            {
                isnnoreach=1;
                dp[0][j]=0;
            }
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(obstacleGrid[i][j]==1) dp[i][j]=0;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

96.不同的二叉搜索树

题目链接：96. 不同的二叉搜索树 - 力扣（LeetCode）

这个题目是给出一个递增序列，判断可以组成多少种不同的二叉搜索树。对于dp[i]的含义，我们定义为i个节点能组成的二叉搜索树的个数。对于递推公式，我们遍历所有的节点，该节点的左子树的个数乘上右子树的个数，就是以该节点和根节点的二叉搜索树的个数，当左子树或右子树为空就直接把不为空的二叉搜索子树的个数进行赋值。对于初始化，dp[0]=0,dp[1]=1,dp[2]=2。具体代码实现如下所示：
 

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+10,0);
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(dp[j-1]==0) dp[i]+=dp[i-j];
                else if(dp[i-j==0])  dp[i]+=dp[j-1];
                else dp[i]+=dp[j-1]*dp[i-j]; 
            }
        }
        return dp[n];
    }
};