1.dp数组为二维数组,首先我们得知道dp[i][j]的含义,由于求的就是不同路径,那么数组对应的就是,从开始到ij位置下拥有的不用路径。
2.由于关系可知,其实当前位置的路径是左边和上面的和,dp的条件就是:dp[i][j]=dp[i-1][j]+dp[i][j-1];
3.初始化时,我们需注意,第一行与第一列都只有一条路能走,那么初始化第一行与第一列都为1
4.最后返回结果在dp[m-1][n-1];
- class Solution {
- public:
- int uniquePaths(int m, int n) {
- vector
int>> dp(m,vector<int>(n,0)); - for(int i=0;i
- dp[0][i]=1;
- for(int i=0;i
- dp[i][0]=1;
- for(int i=1;i
- {
- for(int j=1;j
- {
- dp[i][j]=dp[i-1][j]+dp[i][j-1];
- }
- }
- return dp[m-1][n-1];
- }
- };
2.不同路径 II
大致思路其实与上一题基本一致。只不过需要对被阻塞的地方对应的dp数组位置数据进行调整。
1.初始化时,如果遇到阻塞,之后的数据一律为0,因为无法走到了
2.由于关系可知,其实当前位置的路径是左边和上面的和,如果没有阻塞dp的条件就是:dp[i][j]=dp[i-1][j]+dp[i][j-1];如果阻塞了,那么dp[i][j]=0
3.最后返回结果在dp[m-1][n-1];
- class Solution {
- public:
- int uniquePathsWithObstacles(vector
int >>& obstacleGrid) { - vector
int>> dp(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),0)); - for(int i=0;i
size();i++) - {
- if(obstacleGrid[i][0]==1)
- break;
- dp[i][0]=1;
- }
- for(int i=0;i
0].size();i++) - {
- if(obstacleGrid[0][i]==1)
- break;
- dp[0][i]=1;
- }
- for(int i=1;i
size();i++) - {
- for(int j=1;j
0].size();j++) - {
- if(obstacleGrid[i][j]==1)
- dp[i][j]=0;
- else
- dp[i][j]=dp[i-1][j]+dp[i][j-1];
- }
- }
- return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
- }
- };
3.最小路径和
本题思路其实也和上面差不多
1.dp数组为二维数组,dp数组表示开始到当前位置的最小路径
2.初始化时,第一行与第一列都只有一条路能走,dp当前位置数据为dp上一次位置的数据加上grid数组当前位置的和
3.由于关系可知,其实当前位置的路径最小和是左边和上面之中较小的那一个加上当前位置路径的大小,条件为dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
- class Solution {
- public:
- int minPathSum(vector
int >>& grid) { - vector
int>> dp(grid.size(),vector<int>(grid[0].size(),0)); - dp[0][0]=grid[0][0];
- for(int i=1;i
size();i++) - dp[i][0]=grid[i][0]+dp[i-1][0];
- for(int i=1;i
0].size();i++) - dp[0][i]=grid[0][i]+dp[0][i-1];
- for(int i=1;i
size();i++) - {
- for(int j=1;j
0].size();j++) - dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
- }
- return dp[grid.size()-1][grid[0].size()-1];
- }
- };
-
相关阅读:
工作流JBPM流程图说明
51单片机复位电容计算与分析(附带Proteus电路图)
【蓝桥杯真题练习】STEMA科技素养练习题库 答案版014 持续更新中~
JS基础之实现数组reduce方法
力扣刷题-字符串-反转字符串Ⅱ
docker 容器
python 获取本机ip
汇编语言是怎么一回事?
护眼灯显色指数多少好?最值得买的护眼灯推荐
XmlBeanDefinitionReader解读
-
原文地址:https://blog.csdn.net/m0_63488627/article/details/130897985