[LeetCode] Unique Paths II

简介: Well, this problem is similar to Unique Paths. The introduction of obstacles only changes the boundary conditions and make some points unreachable (simply set to 0).

Well, this problem is similar to Unique Paths. The introduction of obstacles only changes the boundary conditions and make some points unreachable (simply set to 0).

Denote the number of paths to arrive at point (i, j) to be P[i][j], the state equation is P[i][j] = P[i - 1][j] + P[i][j - 1] if obstacleGrid[i][j] != 1 and 0 otherwise.

Now let's finish the boundary conditions. In the Unique Paths problem, we initialize P[0][j] = 1, P[i][0] = 1 for all valid i, j. Now, due to obstacles, some boundary points are no longer reachable and need to be initialized to 0. For example, if obstacleGrid is like [0, 0, 1, 0, 0], then the last three points are not reachable and need to be initialized to be 0. The result is [1, 1, 0, 0, 0].

Now we can write down the following (unoptimized) code. Note that we pad the obstacleGrid by1 and initialize dp[0][1] = 1 to unify the boundary cases.

 1 class Solution {
 2 public:
 3     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
 4         int m = obstacleGrid.size(), n = obstacleGrid[0].size();
 5         vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));
 6         dp[0][1] = 1;
 7         for (int i = 1; i <= m; i++)
 8             for (int j = 1; j <= n; j++)
 9                 if (!obstacleGrid[i - 1][j - 1])
10                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
11         return dp[m][n];
12     } 
13 };

Well, the code is accepted but it has some obvious redundancy. There are two major concerns:

  1. Each time when we update path[i][j], we only need path[i - 1][j] (at the same column) and path[i][j - 1] (at the left column), so it is unnecessary to maintain the fullm*n matrix. Maintaining two columns is enough.
  2. There are some cases that the loop can be terminated earlier. Suppose obstacleGrid = [[0, 1, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0]], then we can see that it is impossible to reach the bottom-right corner after updating the second column since the number of paths to reach each element in the second column is 0.

Taken these into considerations, we write down the following optimized code.

 1 class Solution {
 2 public: 
 3     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
 4         int m = obstacleGrid.size();
 5         int n = obstacleGrid[0].size();
 6         vector<int> pre(m, 0);
 7         vector<int> cur(m, 0);
 8         for (int i = 0; i < m; i++) {
 9             if (!obstacleGrid[i][0])
10                 pre[i] = 1;
11             else break;
12         }
13         for (int j = 1; j < n; j++) {
14             bool flag = false;
15             if (!obstacleGrid[0][j]) {
16                 cur[0] = pre[0];
17                 if (cur[0]) flag = true; 
18             }
19             else cur[0] = 0;
20             for (int i = 1; i < m; i++) {
21                 if (!obstacleGrid[i][j]) {
22                     cur[i] = cur[i - 1] + pre[i];
23                     if (cur[i]) flag = true;
24                 }
25                 else cur[i] = 0;
26             }
27             if (!flag) return 0;
28             swap(pre, cur);
29         }
30         return pre[m - 1];
31     }
32 }; 

Further inspecting the above code, keeping two vectors only serve for the purpose of recoveringpre[i], which is simply cur[i] before its update. So we can use only one vector and the space is further optimized.

 1 class Solution {
 2 public:
 3     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
 4         int m = obstacleGrid.size();
 5         int n = obstacleGrid[0].size();
 6         vector<int> cur(m, 0);
 7         for (int i = 0; i < m; i++) {
 8             if (!obstacleGrid[i][0])
 9                 cur[i] = 1;
10             else break;
11         }
12         for (int j = 1; j < n; j++) {
13             bool flag = false;
14             if (obstacleGrid[0][j])
15                 cur[0] = 0;
16             else flag = true;
17             for (int i = 1; i < m; i++) {
18                 if (!obstacleGrid[i][j]) {
19                     cur[i] += cur[i - 1]; 
20                     if (cur[i]) flag = true;
21                 }
22                 else cur[i] = 0; 
23             }
24             if (!flag) return 0;
25         }
26         return cur[m - 1];
27     }
28 };

 

目录
相关文章
|
搜索推荐 机器人 SEO
Leetcode 62. Unique Paths & 63. Unique Paths II
原谅我重新贴一遍题目描述,不是为了凑字数,而是为了让搜索引擎能索引到这篇文章,其实也是算一种简单的SEO。 简单描述下题目,有个机器人要从左上角的格子走到右下角的格子,机器人只能向下或者向右走,总共有多少种可能的路径?
36 0
|
Java
Leetcode 467. Unique Substrings in Wraparound String
大概翻译下题意,有个无限长的字符串s,是由无数个「abcdefghijklmnopqrstuvwxy」组成的。现在给你一个字符串p,求多少个p的非重复子串在s中出现了?
49 0
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode 257. Binary Tree Paths
给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。
57 0
LeetCode 257. Binary Tree Paths
|
机器人
LeetCode 63. Unique Paths II
机器人位于m x n网格的左上角(在下图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 现在考虑是否在网格中添加了一些障碍。 有多少条独特的路径?
99 0
LeetCode 63. Unique Paths II
|
机器人
LeetCode 62. Unique Paths
机器人位于m x n网格的左上角(在上图中标记为“开始”)。 机器人只能在任何时间点向下或向右移动。 机器人正试图到达网格的右下角(在下图中标记为“完成”)。 有多少可能的独特路径?
82 0
LeetCode 62. Unique Paths
|
数据安全/隐私保护 C++ Python
LeetCode 804. Unique Morse Code Words
LeetCode 804. Unique Morse Code Words
79 0
Leetcode-Easy 804. Unique Morse Code Words
Leetcode-Easy 804. Unique Morse Code Words
102 0
Leetcode-Easy 804. Unique Morse Code Words
LeetCode之First Unique Character in a String
LeetCode之First Unique Character in a String
116 0
|
算法 机器人 人工智能