本文主要是介绍算法学习 | day34/60 不同路径/不同路径II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目打卡
1.1 不同路径
题目链接:. - 力扣(LeetCode)
拿到手,首先见到答案需要求的是种类的个数,并且看题目,每次移动的时候只有两个方向,这也就说明,对于某一个位置来说,其状态转移的方向来自两个方向,上和左,并且看题,这个题目要求的是总共有多少路径,所以状态应该就是走到当前这个格子一共有多少路径。
(最后看了答案发现我写的有点不对,第一个那个位置应该是1)
再画个图,发现其实这个递推的过程和楼梯一模一样,只是这个变成二维的了:
class Solution {
public:int uniquePaths(int m, int n) {if(m == 0 || n == 0) return 0;// if(m == 1 && n == 1) return 0;// if((m == 1 && n == 2) || (m == 2 && n == 1)) return 1;vector<vector<int>> dp(m+1,vector<int>(n+1,0));// vector<vector<int>> dp(vector<int>(0,m+1),n+1);// for(auto& i : dp){// for(auto & j : i){// cout << j << " ";// }// cout<<endl;// }// dp[1][1] = 0;// dp[1][2] = 1;// dp[2][1] = 1;for(int i = 1 ; i < m + 1;i++){for(int j = 1 ; j < n + 1 ; j++){if(i == 1 && j == 1){dp[1][1] = 1;continue;}if(i == 1 && j == 2){dp[1][2] = 1;continue;}if(i == 2 && j == 1){dp[2][1] = 1;continue;}// if(i == 1 && j == 2) continue;// if(i == 2 && j == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m][n];}
};
我承认比答案写的冗余的多,但是我思路是没问题的😂。
1.2 不同路径II
题目链接:. - 力扣(LeetCode)
拿到题目,第一感觉和上面感觉没什么区别,把障碍物当0不就可以了嘛😂,然后试了试:
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if(obstacleGrid[0][0] == 1) return 0;vector<vector<int>> dp(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),0));// 考虑这种案例,[[0,0],[1,1],[0,0]],如果初始化的时候遇到 障碍物了那么后面都是0for(int i = 0; i < obstacleGrid[0].size();i++){if(obstacleGrid[0][i] == 1){dp[0][i] = 0;break; // 必须要中断,因为这个后面的这个路已经被阻断了}else dp[0][i] = 1;}for(int i = 0; i < obstacleGrid.size();i++){if(obstacleGrid[i][0] == 1) {dp[i][0] = 0;break;}else dp[i][0] = 1;}// test// for(auto& i : dp){// for(auto & j: i){// cout << j << " ";// }// cout << endl;// }//[[1,0]] 这种案例就不会进入循环,所以要在前面处理for(int i = 1 ; i < obstacleGrid.size();i++){for(int j = 1 ; j < obstacleGrid[0].size();j++){if(obstacleGrid[i][j] == 1){dp[i][j] = 0;continue;}dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}}return dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];}
};
差不多调试了几次就通过了,还是有很多不一样的认知的,其实这里面主要是处理障碍物的两种方式,整体思路是遇到障碍物了以后,那个这个路段被阻断,所以就走不到这个位置,但是这里处理的方法在初始化和最后循环是不一样的,初始化的时候,遇到了障碍物,那么一定记住后面所有的都需要置零,而在递推循环中,遇到障碍物以后,是将这个位置的状态,也就是走到这里的路的个数变为0。
这篇关于算法学习 | day34/60 不同路径/不同路径II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!