【力扣刷题 | 第二十二天】

绝地灬酷狼 2024-03-22 20:44 25阅读 0赞

![3916681ad12f4abe8214674e79eca704.jpeg][]

**目录**

前言：

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

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

总结：

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

## 前言： ##

今天我们爆刷动态规划章节的题目，相关的算法理论介绍我也有写过文章：[【夜深人静学数据结构与算法 | 第十篇】动态规划\_][Link 1]，感兴趣的可以看一看，最近家里出事了一直在忙，都没来得及刷题了。

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

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

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

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

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

![85d5e7875d854af39bfbe988dfe160f3.png][]

其实这种动态规划的题，还是严格按照我们动态规划四步走：

1.确定dp数组的含义以及下表的含义

2.递推公式的推到

3.dp数组的初始化

4.dp数组遍历顺序

那么一步一步来：

dp\[i\]\[j\] 的含义就是能够到达坐标为（i，j）位置的路径条数

推导公式：本质上仍然是 dp\[i\]\[j\] = dp\[i-1\]\[j\] + dp\[i\]\[j-1\] 。但是需要做一下微调，因为如果这个地方有障碍物了，那么就不能通过它，要不走包含这个点的路。

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) 
            {
                return 0;
            }
                 vector<vector<int>> dp(m, vector<int>(n, 0));
            for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)
            {
                 dp[i][0] = 1;
            }
            
            for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) 
            {
                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` ），并使这些整数的乘积最大化。

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

![be4319d07f1344df98cac64f69e10d5a.png][]

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

## 总结： ##

今天收获很大。

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

![69e9169c980f43e0aad31ff9ada88a9c.png][]

[3916681ad12f4abe8214674e79eca704.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/27b3c2ae844e42f482c1e29b04774db3.png
[Link 1]: https://blog.csdn.net/fckbb/article/details/131387294?spm=1001.2014.3001.5501
[63. _ II - _LeetCode]: https://leetcode.cn/problems/unique-paths-ii/
[85d5e7875d854af39bfbe988dfe160f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2332e4f8a2d4460cbfce8b7a7044b345.png
[343. _ - _LeetCode]: https://leetcode.cn/problems/integer-break/
[be4319d07f1344df98cac64f69e10d5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/befaae5c0f31490a8b4300f284567cdc.png
[69e9169c980f43e0aad31ff9ada88a9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/81c4921a0d434edb95be9016a2a724c0.png