leetcode_day36

今日内容：

• 62. 不同路径 medium
• 63. 不同路径Ⅱ medium
• 343. 整数拆分 medium
• 96. 不同的二叉搜索树 medium

62. 不同路径

题目：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

思路：

由于方向定死只能朝着目标走，不允许走回头路，所以走到一个格子只可能从其左边或上面来到，那么这就不难直接想出递推公式：

\[ dp[i][j] = \begin{cases} 1, & \text {$i = 1 or j = 1$} \\ dp[i - 1][j] + dp[i][j - 1], & \text {else} \end{cases} \] dp[i][j]表示从起点走到第[i, j]格的所有路径数

代码

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

63. 不同路径Ⅱ

题目：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

思路：

其实思路差不多，由于笔者追求尽可能少的改动，只加了一行代码就想过关，结果被特殊用例坑了两发WA😭，怎么障碍物会出现在起点和终点啊，落地成盒+通天河老鼋是吧🤡

仍然动态规划，只是状态转移方程要改一下，应该遍历整个地图，如果发现障碍物，就把这一格的dp置零表示此路不通，由于笔者代码有点问题，所以还另有改动，在地图边缘的格子不能无脑置1，得继承上一格数值，防止跳过了障碍物。

carl的代码也有类似思想

代码

个人代码

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

官解代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
        vector <int> f(m);//压缩了dp数组

        f[0] = (obstacleGrid[0][0] == 0);//起点能不能走
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {//遇障置零
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0) {//非首列
                    f[j] += f[j - 1];
                }
            }
        }

        return f.back();
    }
};

利用滚动数组压缩空间，滚动数组就是上一篇只用3个变量来压缩整个dp数组的思想，抛弃掉之前不用的状态，只获取最终状态，这里也一样，从上到下的路径是继承的，而从左到右的路径是累加的。而外层大循环就是改变行，每行都会继承上一行的结果。

343. 整数拆分

题目：

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

思路：

本来该用dp的，但是数学直觉给我指了另一条路，高中学过基本不等式，有口诀为“和定积最大，积定和最小”，而此处就是“和定”，由基本不等式最值条件可知，每个数应该尽量相等（尽量是因为得是整数，不然必须相等），而拆分的数量简单一推就知道先增后减：

比如12：

• 分为2个数：\(6*6=36\)
• 分为3个数：\(4 * 4 * 4 = 64\)
• 分为4个数：\(3^4=81\)
• 分为5个数：\(2 * 2 * 2 * 3 * 3 = 72\)
• 分为6个数：\(2^6=64\)

先增后减，所以从2开始一直增加拆分数，一旦积开始减少，就说明到达最值点了。

官解的数学证明好复杂，看起来很抽象啊，导数大题只得了6分的我看不懂，还是不等式选修秒杀更舒服

代码

class Solution {
public:
    //和定积最大，基本不等式定调均分
    //随便举几个例子可大致知道k先增后减，存在峰值
    //但均分不好实现，如10分为2233或2224，均分应该使方差最小
    //逐步除法也许可以实现最均分，尝试一下
    int integerBreak(int n) {
        int ans = 0;
        for(int k = 2;k <= n;k++) {//等分数量
            int m = n, temp = 1;
            for(int i = k;i > 0;i--) {//已经获得的加子数量
                temp *= m / i;
                m -= m / i;
            }
            if(temp > ans) ans = temp;
            else break;
        }
        return ans;
    }
};

均分方法蒙对了，没严格证明，至少能AC

96. 不同的二叉搜索树

题目：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

思路：

有点多项式定理的感觉，沉睡的高中数学之魂复燃？，画图可能比较好理解，但是图书馆要闭馆了，没时间画图了。

根据其示例可以得到提示：以不同的数做根来分类讨论，以4为例

• 若1作根，则剩余3个数形成的BST个数就是当前BST的个数总数，由示例得到为5
• 若2作根，则剩余2个数3、4只能在右子树，当前BST总数就是2节点BST的总数2
• 若3作根，则4只能在右子树，左子树是2节点BST总数2
• 若4作根，则1、2、3都在左子树，就是3节点BST总数，5

所以4节点BST总数为5+2+2+5。

由此发散，联想多项式定理，可得状态转移方程：

\[ dp[i] = \begin{cases} 1, & \text {$i = 0 or i = 1$} \\ \sum_{root=1}^i (dp[root-1]*dp[i-root]), & \text {$i > 1$} \end{cases} \]

dp[i] 代表有i个节点的BST种数;

代码

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++) {//节点数
            int temp = 0;
            for(int root = 1;root <= i;root++) {//谁做根
                temp += dp[root - 1] * dp[i - root];
            }
            dp[i] = temp;
        }
        return dp[n];
    }
};