欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 八卦 > 代码随想录算法训练营Day36| 62.不同路径 , 63. 不同路径 II

代码随想录算法训练营Day36| 62.不同路径 , 63. 不同路径 II

2025/2/24 20:04:54 来源:https://blog.csdn.net/2401_82757749/article/details/140007974  浏览:    关键词:代码随想录算法训练营Day36| 62.不同路径 , 63. 不同路径 II

由于我最近临近期末考试所以后面两题就先暂时跳过,但是并不是代表我不写,等我暑假会全部补起来,那么来看今天的第一题

62.不同路径:代码随想录

这道题目就是说让你求出到达终点有几种不同的路径,你只能向下或者向右走,那么直接开始我们的动规五部曲!

首先就是dp数组的含义,这里的含义很显然就是到当前点有几种不同的路径,下标表示的就是该点的坐标,然后就是初始化,我就是在初始化这里犯了错误,这里我们是要将数组的第一排和第一列全部初始化为1,因为这些位置全部只能由起点到达,因为题目说了只能向下或者向右走,而我一开始就只是将两个位置初始化了,所以后面就出问题了,这里也再次说明了初始化的重要性,然后就是递推公式,这就非常简单了,很显然,这点只能由上面的点和左边的点到达,所以递归公式就是dp[i][j]=dp[i][j-1]+dp[i-1][j],还需注意的是,我这里遍历的时候下标是从1开始的,所以不需要担心下标越界的问题,遍历顺序就很简单了,因为我们是从当前位置向右和下走,所以肯定是从左往右,从上到下遍历,这就不难写出如下代码

class Solution {
public:int uniquePaths(int m, int n) {int dp[m][n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){dp[i][0]=1;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];}
};

63. 不同路径 II:代码随想录

这道题目和上道题目是一样的,只不过是加了一些障碍物,这就意味着我们需要考虑一些特殊情况,首先就是初始化因为我们知道,如果说起点和终点就有障碍物的话,那肯定是直接返回0了,如果说在第一排或者是第一列出现障碍物,那是不是代表后面的点我都无法到达了,因为这些点只能由起点到达,所以只要我发现了障碍物,我就将后面所有的点都放上障碍物,也就是说后面的点都无法到达了,也就是将相应的数组的值赋值成1,然后就是递推公式的改变,首先如果我们当前遍历的点是障碍物的话,是不是直接continue就可以了,如果不是,我们还要在上面一题的基础上分情况讨论,有障碍物的就不能到达这点,所以我们可以写出如下代码

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

只需要在对应的情况分类讨论即可,这就是今天的内容了,比较少,因为后面两道难题我没时间做,我后面有时间做一定会补上!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词