LeetCode 0063 - Unique Paths II
# Hints
- DP
# 前置题目
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
A robot is located at the top-left corner of a grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as and respectively in the grid.
Note:
and will be at most .
Example 1:
Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
# 题意
有一个 的网格,其中若干个格子有障碍物,初始站在 处,每一步只能向右或向下移动,求走到 处有多少种不同的移动方案。
# 题解
与 LeetCode 0062 相比,动态规划的方法仍然适用,而组合数学的方法则不再可用。
我们只需在状态转移方程的基础上,对每个存在障碍物的位置 ,在递推时追加强制 即可,总的时间复杂度仍为 。
# AC代码
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>> & obstacleGrid) {
// 初始化
int m = obstacleGrid.size(), n = obstacleGrid.front().size();
int dp[m][n];
// 递推
dp[0][0] = (obstacleGrid[0][0] == 0 ? 1 : 0);
for (int i = 1; i < m; i ++) {
dp[i][0] = (obstacleGrid[i][0] == 0 ? dp[i - 1][0] : 0);
}
for (int j = 1; j < n; j ++) {
dp[0][j] = (obstacleGrid[0][j] == 0 ? dp[0][j - 1] : 0);
}
for (int i = 1; i < m; i ++) for (int j = 1; j < n; j ++) {
dp[i][j] = (obstacleGrid[i][j] == 0 ? dp[i - 1][j] + dp[i][j - 1] : 0);
}
// 返回
return dp[m - 1][n - 1];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01