【力扣刷题 | 第十五天】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【力扣刷题 | 第十五天】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【力扣刷题 | 第十五天】,【力扣刷题】,leetcode,算法,数学建模

前言：

63. 不同路径 II - 力扣（LeetCode）

343. 整数拆分 - 力扣（LeetCode）

总结：

前言：

本篇我们主要刷动态规划的题，解题还是严格按照我们在【夜深人静写算法】栏目下的解题步骤，大家如果没学过动态规划的可以先看看我写的动态规划文章介绍。

【夜深人静学数据结构与算法 | 第十篇】动态规划_我是一盘牛肉的博客-CSDN博客

文章来源地址https://www.toymoban.com/news/detail-614206.html

63. 不同路径 II - 力扣（LeetCode）

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

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

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

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

【力扣刷题 | 第十五天】,【力扣刷题】,leetcode,算法,数学建模其实这题跟我们在动态规划中讲解的例题答题思路基本一致，就是需要再加一个判断条件：
如果这块是障碍点，那么我们就将这个点的路径数设置为0，并且放弃这条路。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
	if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍，直接返回0
       { 
            return 0;
       }    
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)//obstacleGrid[i][0] == 0也就是没有障碍物
        {
            dp[i][0] = 1;
        } 
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++)// obstacleGrid[0][j] == 0也就是没有障碍物
        {
             dp[0][j] = 1;
        };

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

    }
};

343. 整数拆分 - 力扣（LeetCode）

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

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

【力扣刷题 | 第十五天】,【力扣刷题】,leetcode,算法,数学建模

其实这道题我们要明白：要想使得拆出来的整数乘积大，我们就要尽量的保证拆出来的整数接近。也就是尽可能拆出来相同的数。

关于为什么是这样的，我们需要用数学公式解决：

这个问题可以通过数学方法进行解释，思路如下：

假设将整数 n 拆分成 k 个正整数相加，这 k 个正整数分别为 a1, a2, ..., ak，则它们的乘积为：

P = a1 * a2 * ... * ak

我们可以对这个乘积进行求导，得到：

dP/da1 = a2 * a3 * ... * ak
dP/da2 = a1 * a3 * ... * ak
...
dP/da(k-1) = a1 * a2 * ... * a(k-1)
dP/da(k) = a1 * a2 * ... * a(k-1)

由于这k个正整数相加得到的和为n，因此有：

a1 + a2 + ... + ak = n

可以使用拉格朗日乘数法求解上面的一组方程，得到：

a1 = n / k
a2 = n / k
...
ak-1 = n / k
ak = n - (k-1) * n / k

可以看到，当 k 越大时，每个数都越趋近于相等，因此其乘积也会越来越大，直到取到最大值。

因此，我们可以通过枚举每个 k，来找到乘积最大的 k 和对应的乘积。

看不懂也没有关系，知道这个结论就可以了，但是如果更好的理解这个数学验证的话，我们就可以在验证的时候做更好的优化。

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

但其实本道题还可以用贪心算法的思路来做，但是贪心算法的代码虽然简洁，但是数学公式证明起来比较麻烦。

本题是可以用贪心算法进行求解的。

1. 当n>=5时，将n拆分成3和n-3的和，比将其拆分成2和n-2的和要优秀，即：

n-3 > n-2 && 3*(n-3) > 2*(n-2)

这个性质可以通过一系列代数计算证明。

2. 当n>=5时，将n拆分成3的个数不会小于将其拆分成2的个数，即：

n mod 3 <= 1

这个性质也可以通过一系列代数计算证明。

基于以上结论，可以采用贪心算法，将整数n尽可能地拆分成3的和，直到最后得到的整数小于5。如果最后得到的整数等于1，则将其与最后一个3合并为4。

这种贪心策略的正确性可以通过数学归纳法证明。这里只给出其中一个例子：

当n=6时，根据以上贪心策略，将其拆分成3和3的和，乘积为9。然而，将其拆分成2和2和2的和，乘积为8，不是最优解。但是，当n=5时，按照贪心策略，将其拆分成3和2的和，乘积为6；而将其拆分成2和3的和，乘积为5，不是最优解。又因为任何大于5的整数都可以通过一系列的拆分得到6和2或3的和，因此对于所有大于5的整数，采用贪心策略是最优的。

因此，可以使用贪心算法来解决这个问题。

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        int result = 1;
        while (n > 4) {
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
};