分类信息网站模板,南昌企业建站,饮品网页设计图片,微信公众平台注册平台迷宫问题是比较经典的算法问题#xff0c;一般可以用动态规划、回溯等方法进行解题#xff0c;这道题目是我昨晚不同路径这道题趁热打铁继续做的#xff0c;思路与原题差不多#xff0c;只是有需要注意细节的地方#xff0c;那么话不多说#xff0c;直接上coding和解析一般可以用动态规划、回溯等方法进行解题这道题目是我昨晚不同路径这道题趁热打铁继续做的思路与原题差不多只是有需要注意细节的地方那么话不多说直接上coding和解析
题目描述
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示。
解析
如果做过类似迷宫问题的读者对于这道题目的思路想必也会第一时间想到仍然使用动态规划的思路去解答但是对于路径中的障碍物在这里却需要着重的单独讨论因为有了障碍物那么对于部分目标点的路径数会发生改变。此题目中需要考虑的特殊位置有如下图所示 所画图给出了一种情况下的各个点下的路径数可以看到对于紫色笔给出的新的当前的节点路径数仍满足原始状态下的dp[i][j] dp[i-1][j]dp[i][j-1]的动态递推式但对于有障碍的节点不满足那么障碍节点可达到路径数直接为0对于迷宫问题当前节点的可通行路线是由当前节点的左侧节点和正上方节点的可通过路径数相加得到那对于左上方存在障碍的情况当前节点的可通过数就需要变化。如下图所示。 这是相对于原始题目的第一处变化考虑了障碍物那么就得讨论一下障碍物在某些特殊位置下的特殊情况比如障碍物在初始行、列上的时候比如 这种情况下我们就不能单纯的只能把障碍物所处的位置上的路径数置为0而是要把往后的那一列/一行上的数据都要置为0为什么因为机器人只能向下或者向右走所以对于初始行、列上的障碍物往后的点机器人是无法到达的 当然还剩下最后一个情况起点就有障碍物那直接return 0咯~
代码
1.初始化dp数组
//初始化dp数组我这里全给的-1方便后续判别障碍物、无障碍物和路径数
int dp[110][110];for(int i0;i110;i){for(int j 0;j110;j){dp[i][j] -1;}}2.根据地图将地图中障碍物所处对应的dp数组位置置路径数为0
for(int i0;iobstacleGrid.size();i){for(int j0;jobstacleGrid[i].size();j){if(i 0 j 0){//起点是障碍物if(obstacleGrid[i][j] 1){return 0;}}if(i 0){//障碍物在初始行上if(obstacleGrid[i][j] 1){for(int m j;mobstacleGrid[i].size();m){dp[i][m] 0;}}}if(j 0){//障碍物在初始列上if(obstacleGrid[i][j] 1){dp[i][j] 0;for(int x i1;xobstacleGrid.size();x){dp[x][j] 0;}}}else if(i ! 0 j! 0){//障碍物不在特殊位置上那直接对应位置dp设置为0即可if(obstacleGrid[i][j] 1){dp[i][j] 0;}}}}3.计算dp数组
for(int i0;iobstacleGrid.size();i){for(int j0;jobstacleGrid[i].size();j){if(i 0 || j 0){if(dp[i][j] -1){dp[i][j] 1;}}if(i ! 0 j ! 0){if(dp[i][j] ! 0){dp[i][j] dp[i-1][j] dp[i][j-1];}}}}4. 完整代码和结果
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {// 跟第一种情况是一样的只是对于地图中有障碍物的地方对应的dp数组置为1int dp[110][110];for(int i0;i110;i){for(int j 0;j110;j){dp[i][j] -1;}}for(int i0;iobstacleGrid.size();i){for(int j0;jobstacleGrid[i].size();j){if(i 0 j 0){if(obstacleGrid[i][j] 1){return 0;}}if(i 0){if(obstacleGrid[i][j] 1){for(int m j;mobstacleGrid[i].size();m){dp[i][m] 0;}// break;}}if(j 0){if(obstacleGrid[i][j] 1){dp[i][j] 0;for(int x i1;xobstacleGrid.size();x){dp[x][j] 0;}// break;}}else if(i ! 0 j! 0){if(obstacleGrid[i][j] 1){dp[i][j] 0;}}}}for(int i0;iobstacleGrid.size();i){for(int j0;jobstacleGrid[i].size();j){if(i 0 || j 0){if(dp[i][j] -1){dp[i][j] 1;}}if(i ! 0 j ! 0){if(dp[i][j] ! 0){dp[i][j] dp[i-1][j] dp[i][j-1];}}// else{// dp[i][j] dp[i-1][j] dp[i][j-1];// }}}coutdp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];}
};总结
个人感觉这类题目是十分具有代表性的动态规划算法题 为什么这么说因为动态规划要满足最优子结构而恰恰这类题的子结构十分清晰就比如我要知道当前位置有几种路径可以到达就可以直接从我的前一步也就是我的左边那一步和正上面的那一步就能到达也就是我的左边和上面是与我当前可联通的那么就直接得到了我当前的可通行路径数。有的人可能会说那这样的话应该是两者之和再加1才是最终的路径数呀 其实不然我最开始也陷入了这样的思维模式中去了而其实应该这么想我们所要求的是路径而不是步数讨论的不是走了几步而是有几种到达的方法换言之就是只要我能到达左边那个位置或者上面那个位置那么我一定能够到达当前所求的这个位置那么也就说明到达上面/左边位置的路径均能到达我当前的位置那么两个地方的路径数之和就是到达当前位置的路径数之和~ 这里就不贴图了 如果文字描述不清楚可以结合上面的xyz那张图也就是所有图中的第三张图进行结合理解。 动态规划变种很多前些时候做了些公司面试笔试题 发现很多题可以用动态规划来做但是不得其解文中的题目是比较清晰的容易推出动态规划递推式的类型对于一些变种还需要多做多总结欢迎各位读者在评论区进行讨论有更好的方法我也很愿意与您交流学习 如果文章对您有帮助可以点个小赞哦~
