【力扣刷题 | 第十五天】

Bertha 。 2024-03-16 23:15 122阅读 0赞

![af18dbee1d9146d6b43c341bafded991.jpeg][]

**目录**

前言：

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

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

总结：

--------------------

## 前言： ##

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

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

## [63. 不同路径 II - 力扣（LeetCode）][63. _ II - _LeetCode] ##

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

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

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

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

![77b89433ad67459da1104d93977d9557.png][]其实这题跟我们在动态规划中讲解的例题答题思路基本一致，就是需要再加一个判断条件：  
**如果这块是障碍点，那么我们就将这个点的路径数设置为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）][343. _ - _LeetCode] ##

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

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

![5aa02b2e01804a8e9a277d6db6612526.png][]

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

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

> 这个问题可以通过数学方法进行解释，思路如下：
> 
> 假设将整数 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;
        }
    };

## 总结： ##

在做动态规划的时候，我们如果是初学的话，要牢牢按照动态规划五步走，这样才可以完整的解题，而不是稀里糊涂的看题解。

如果我的内容对你有帮助，请**点赞，评论，收藏**。创作不易，大家的支持就是我坚持下去的动力！

![69e9169c980f43e0aad31ff9ada88a9c.png][]

[af18dbee1d9146d6b43c341bafded991.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/fccf624ece0448a4aba7b88bd1f622af.png
[_ _-CSDN]: https://blog.csdn.net/fckbb/article/details/131387294
[63. _ II - _LeetCode]: https://leetcode.cn/problems/unique-paths-ii/
[77b89433ad67459da1104d93977d9557.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/85d6c0f309564565bb42d3a973b59763.png
[343. _ - _LeetCode]: https://leetcode.cn/problems/integer-break/
[5aa02b2e01804a8e9a277d6db6612526.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/fb06305007304904b6123f70dc73e722.png
[69e9169c980f43e0aad31ff9ada88a9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/adef2ed13e074241b4e17197e89f25a1.png