力扣刷题记录（16）LeetCode：62、63、343、96

目录

62.?不同路径

63.?不同路径 II?

343.?整数拆分?

?96.?不同的二叉搜索树

总结?

---

这题比较简单，直接声明一个二维数组来保存到达该点有几种路径。到达当前点的方法由当前点的左边格子和右边格子决定。

class Solution {
public:
    int uniquePaths(int m, int n) {

        vector<vector<int>> mesh;
        for(int i=0;i<m;i++)
        {
            vector<int> row;
            for(int j=0;j<n;j++)
            {
                //如果是第一行
                if(i==0)
                {
                    row.push_back(1);
                }
                //不是第一行
                else
                {
                    if(j==0)    row.push_back(mesh[i-1][j]);
                    else    row.push_back(mesh[i-1][j]+row[j-1]);
                }
            }
            mesh.push_back(row);
        }
        return mesh[m-1][n-1];
    }
};

63.?不同路径 II?

?

这题与上题类似，就是在确定到达当前点的路径总数时判断一下上方及左方是否有障碍物。一共分三种情况。

1.上方有障碍

2.左方有障碍

3.都没障碍

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        for(int i=0;i<obstacleGrid.size();i++)
        {
            for(int j=0;j<obstacleGrid[0].size();j++)
            {
                if(obstacleGrid[i][j]==1)
                {
                    obstacleGrid[i][j]=-1;
                    continue;
                }   
                //第一行
                if(i==0)
                {
                    if(j==0)    obstacleGrid[i][j]=1;
                    else
                    {
                        //左边有障碍物
                        if(obstacleGrid[i][j-1]==-1)    obstacleGrid[i][j]=0;
                        //左边无障碍物
                        else    obstacleGrid[i][j]=obstacleGrid[i][j-1];
                    }
                }
                //非第一行
                else
                {
                    //第一列
                    if(j==0)
                    {
                        if(obstacleGrid[i-1][j]==-1)    obstacleGrid[i][j]=0;
                        else    obstacleGrid[i][j]=obstacleGrid[i-1][j];
                    }
                    //非第一列
                    else
                    {
                        if(obstacleGrid[i-1][j]==-1)    obstacleGrid[i][j]=obstacleGrid[i][j-1];
                        else if(obstacleGrid[i][j-1]==-1)   obstacleGrid[i][j]=obstacleGrid[i-1][j];
                        else    obstacleGrid[i][j]=obstacleGrid[i][j-1]+obstacleGrid[i-1][j];
                    }
                }
            }
        }
        if(obstacleGrid[obstacleGrid.size()-1][obstacleGrid[0].size()-1]==-1)   return 0;
        return obstacleGrid[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
    }
};

343.?整数拆分?

?

这题也是典型的动态规划，要想知道当前值如何拆分能够使乘积最大要利用比它小的值如何拆分乘积最大。比如10，我们先将其拆分成两个数，[[1,9],[2,8],[3,7],[4,6],[5,5]]有这5种拆分方式。如果我们前面已经得到了[9,8,7,6,5]的最大拆分乘积，那遍历这几种情况就可以得到最大值啦。

注意：每种情况我们可以选择拆或者不拆，比如[3,7]，我们可以不拆，也可以将它拆成[3,3,4]。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i / 2; j++) 
            {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

?96.?不同的二叉搜索树

?

这道题要找到状态转移方程，n个结点的二叉搜索树的数量与小于n个结点的二叉搜索树的数量有关联。?比如n=3，1为头结点时左边一定是0个元素、右边一定是两个元素（右边有多少种情况就是dp[2]），2为头结点时左边一定是1个元素(dp[1])、右边一定是一个元素dp[1]，3为头结点时左边一定是两个元素(dp[2])、右边一定是0个元素(dp[0])。所以dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]。

由此可以推导出状态转移方程，dp[i]+=dp[j-1]*dp[i-j]。j是从1到n循环，代表头结点的值。i表示结点总数。

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=1;

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

总结?

动态规划的难点在于如何才能找到动态转移方程。动态规划是解决由重复子问题所构成的大问题。所以要从题目中提取出这个重复的子问题是什么。?