题目链接:leetcode不同路径II
目录
题目解析:
算法原理
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码
题目解析:
题目让我们求在考虑网格中有障碍物的情况下,从左上角到右下角将会有多少条不同的路径
由题可得:
机器人位于一个 m x n
网格的左上角
机器人每次只能向下或者向右移动一步
我们拿示例1来分析:
则根据题目要求我们只能向下或者向右移动一步,不能向上或向左回退,而且要避开障碍物;
所以这里我们一共有2种走法:
算法原理:
1.状态表示
先创建一个dp表
首先先思考dp表里面的值所表示的含义(是什么?)
dp[i][j]表示到达i*j时一共有多少种方式;
这种状态表示怎么来的?
1..经验+题目要求
用之前或者之后的状态,推导出dp[i][j]的值;
根据最近的最近的一步,来划分问题
经验:以i*j位置为结尾,
题目让我们求到达右下角有多少种方式(需要避开障碍物),那么这里我们可以dp[i][j]来表示。
所以这里我们用i*j表示右下角位置;
2.状态转移方程
dp[i]等于什么?
我们先不考虑有障碍物的情况:
当机器人到达dp[i-1][j]时,我们知道它到达[i-1][j]有dp[i-1][j]方式,
此时只需要从[i-1][j]往下走一步就可以到达目标位置,即:
……-->[i-1][j]-->(往下走一步)[i][j];
……-->[i-1][j]-->(往下走一步)[i][j];
……-->[i-1][j]-->(往下走一步)[i][j];
……
所以往下走一步就可以到达目标位置的方式就有dp[i-1][j]种;
那么同理,
当机器人到达dp[i][j-1]时,我们知道它到达[i][j-1]有dp[i][j-1]方式,
此时只需要在到达[i][j-1]方式的后面往右边走一步就可以到达目标位置,即:
……-->[i][j-1]-->(往右边走一步)[i][j];
……-->[i][j-1]-->(往右边走一步)[i][j];
……-->[i][j-1]-->(往右边走一步)[i][j];
……
所以往右边走一步就可以到达目标位置的方式就有dp[i-1][j]种;
综上所述,我们只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到,到达[i][j]位置的总方法,
即:
dp[i][j]=dp[i-1][j]+dp[i][j-1];
好,分析完了没有障碍物的情况,现在我们再来加上障碍物:
从上面的分析我们知道到达i*j位置,只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到
如果[i][j-1]与[i-1][j]之中有一个是障碍物时:
那么有效的路线就只有上面那条,那么只要把有障碍物的地方设为0,就不会影响状态转移方程了。
3.初始化
(保证填表的时候不越界)
由我们的状态转移方程得:
在0行0列的时候越界,所以我们这里可以在m*n的外围多加1行1列,如图:
还有一个问题是:
我们要拿新增用来初始化的行和列要初始化为几呢?
假设:如果所需要到达的位置就在机器人所在的位置,此时有一种方式;
根据状态转移方程,在[0][1]与[1][0]位置要有一个位置需要初始化为1,其他位置初始化为0
我们这里选择[0][1]初始化为1
4.填表顺序
(为了填写当前状态的时候,所需要的状态已经计算过了)
这里所需要的状态是:到达该位置的上面和左边位置的方式
所以填表顺序:
从上到下填写每一行
从左到右填写每一列
5.返回值
(根据题目要求和状态表示)
综上分析:
返回值为:dp[m][n];
编写代码:
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//1.创建dp表
//2.初始化
//3.填表
//4.返回结果
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
dp[0][1]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(obstacleGrid[i-1][j-1]==1)
{
dp[i][j]=0;
}
else
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}
};