当前位置：首页 > news >正文

代码随想录算法训练营第60期第三十七天打卡

news 来源：原创 2025/6/23 6:19:55

大家好，今天我们算法训练营的第37天，首先为自己感到骄傲，居然坚持下来了，本来觉得自己可能坚持不下来，但是我硬是坚持下来了，好样的，同时也感谢那些看我的题解给我点赞的朋友，我在这里表示衷心的感谢，祝愿你们算法之路和求职之路顺利，好的，那么我们今天就继续我们的动态规划，我提到过其实动规还是很难的，今天开始就会逐渐上难度，我们就开始今天的题目。

第一题对应力扣编号为62的题目不同路径

我们来到今天的第一题，这道题目就开始有dp的感觉了，我们一起来看一下题目：

其实这道题目是寻找所有可达路径的问题，就是机器人起初在左上角需要去到右下角，然后机器人每一次还只能向下或者向右移动一步，其实我开始接触这道题目的时候感觉这像是图论里面的所有可达路径那道题目，就要使用深度优先搜索去解决，如果我们使用深度优先搜索的话我们是搜索一棵二叉树，我们就将这个地图抽象成一棵二叉树，这个其实时间复杂度还是很高的，大家在图论里面就会真正理解深度优先搜索究竟在图论里面是如何使用的，在这里我们很明显要去使用动态规划，我们先定义dp数组，这个dp数组是一个二维数组，表示的是从左上角的点到当前点的所有路径的条数，我们需要考虑的一个很重要的问题就是如何初始化，这个还是不好想的，其实我就直接告诉大家，我们存在一种比如说我要到第一行的某个点，其实我是只有1种可达路径的，因为我们规定了只能向上或者向右，如果我留在第一行不动的话一旦我们向下了就不可能留在第一行了因为我们是不可以向上走的，同理我们如果要留在第一列的话我们一样一旦我们向右走了我们就不可以去到我们的目标点了，因此我们的初始化就有思路了，就是第一行和第一列都是1，遍历顺序这个没什么好说的，一定是从起点到终点，状态转移方程就是这一个点是它上面的点和左边的点转移来的，这就可以了，我们看一下解题代码应该如何写：

class Solution {
public:int uniquePaths(int m, int n) {//dp表示的是从(1, 1)到某个点不同路径的条数vector<vector<int>> dp(m, vector<int>(n, 0));//注意初始化for (int i = 0; i < m; ++i) dp[i][0] = 1;//只能向下否则一旦向右了不允许向左就回不来了for (int j = 0; j < n; ++j) dp[0][j] = 1;//同理一旦向下了就不能向上for (int i = 1; i < m; ++i){for (int j = 1; j < n; ++j){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};

这个其实不难理解，最后输出的应该是dp[m-1][n-1]这是考虑到了索引的问题，包括二维数组的定义大家也要学会在后面图论会经常遇到，接下来就是状态转移方程与初始化，大家还是按照动规五部曲来解决这道题目就可以。

第二题对应力扣编号为63的题目不同路径 II

这一道题很明显与上一道题目是类似的题目，但是一定存在不一样的地方否则不就是一道题目了，我们来看一下这一道题目有什么不一样的地方：

这里是增加了障碍物，有障碍物的路不可以走，其实比起上一道题目是增加了一些需要处理的细节，就是这个障碍物的问题，首先就有可能存在一种情况就是我们的起点或者终点就是障碍物点这时候直接返回0，因为根本无路可走，有朋友可能感觉这种情况就是多想了，其实不一定因为写代码一定要严谨，我们需要考虑所有可能会发生的情况，接下来其实就与上一道题目没有什么不一样的地方了，不过就是障碍物的地方就是0，因为无路可以走到这里，我们直接看一下代码：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 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];}
};

重点就是有障碍物的地方我们需要continue掉，其他的点正常统计还是与上一题一样的转移方程，初始化也是注意障碍物的点就可以了。接下来我们挑战一道有难度的题目。

第三题对应力扣编号为343的题目整数拆分

这是今天的第一道选做题，一刷代码随想录是可以跳过的，但是我要去挑战一下，我们一起来看一下题目是什么意思：

这个是我把一个整数拆分成k个正整数的和，同时需要满足这些整数的乘积要最大化，这个其实需要一点数学知识，我们什么请况下的乘积是最大的，比如说9可以9+0，1+8，2+7，3+6，4+5很明显乘积最大的是5*4 = 20其实就是这些整数挨得最近的时候，其实我们也知道平方其实就是最大值，这就是本道题目的关键思路，首先我们还是使用动规五部曲来解决，还是先定义dp数组就是dp[n]表示正整数n拆分以后乘积的最大值，其实题目并没有告诉我们要拆成几个数字的乘积，这里就很有难度了，我们dp[i]就有两种可能的途径，第一种j*(i - j)这其实表示的是两个数的乘积，j * dp[i - j]这个是表示i-j还可以再分解，这个思路很重要，我们初始化就不难了，dp[2] = 1才有效，dp[1]无法拆成k个正整数的和所以就是0直接初始化了，接下来我们就遍历，其实大家知道我们两个数相等的时候乘积就是最大的，根据这个思想我们可以找到遍历的范围，尤其是分解出来的数，这样我们就可以写出如下解题代码：

class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[2] = 1;//注意dp数组的含义是（分解后乘积的最大值）for (int i = 3; i <= n; ++i){for (int j = 1; j <= i / 2; ++j){//注意dp数组的含义dp[i-j]表示i-j其实还可以继续拆解因为拆成的数不管有几个数值接近的时候取最大值的概率更大dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j)));}}return dp[n];}
};

大家注意的就是我们的j的取值范围还有一个就是我们分解的数都是不固定的就可以了，其实题目可能难在存在一定的数学思维。

今日总结

今天我们的题目已经具备了动态规划的思想，接下来可能难度会越来越大，牢记动规五部曲，如果代码看不懂的话就去思考我的dp数组的含义究竟是什么，接下来我们就会进入背包问题，这个是动态规划很重要的问题，我们下一次博客再见！

第一题对应力扣编号为62的题目不同路径

第二题对应力扣编号为63的题目不同路径 II

第三题对应力扣编号为343的题目整数拆分

今日总结

相关文章：