4ms O(n) DP Solution in C++ with Explanations
Well, this problem is similar to Unique Paths. The introduction of obstacles only changes the boundary conditions and make some points unreachable (simply set t
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`).\n\nDenote 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. \n\nNow 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]`.\n\nNow we can write down the following (unoptimized) code. Note that we pad the `obstacleGrid` by `1` and initialize `dp[0][1] = 1` to unify the boundary cases. \n\n    class Solution {\n    public:\n        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n            int m = obstacleGrid.size(), n = obstacleGrid[0].size();\n            vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));\n            dp[0][1] = 1;\n            for (int i = 1; i <= m; i++)\n                for (int j = 1; j <= n; j++)\n                    if (!obstacleGrid[i - 1][j - 1])\n                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];\n            return dp[m][n];\n        } \n    };\n\nWell, the code is accepted but it has some obvious redundancy. There are two major concerns:\n\n 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 full `m*n` matrix. Maintaining two columns is enough.\n 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`.\n\nTaken these into considerations, we write down the following optimized code.\n    \n    class Solution {\n    public: \n        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n            int m = obstacleGrid.size();\n            int n = obstacleGrid[0].size();\n            vector<int> pre(m, 0);\n            vector<int> cur(m, 0);\n            for (int i = 0; i < m; i++) {\n                if (!obstacleGrid[i][0])\n                    pre[i] = 1;\n                else break;\n            }\n            for (int j = 1; j < n; j++) {\n                bool flag = false;\n                if (!obstacleGrid[0][j]) {\n                    cur[0] = pre[0];\n                    if (cur[0]) flag = true; \n                }\n                else cur[0] = 0;\n                for (int i = 1; i < m; i++) {\n                    if (!obstacleGrid[i][j]) {\n                        cur[i] = cur[i - 1] + pre[i];\n                        if (cur[i]) flag = true;\n                    }\n                    else cur[i] = 0;\n                }\n                if (!flag) return 0;\n                swap(pre, cur);\n            }\n            return pre[m - 1];\n        }\n    }; \n\nFurther inspecting the above code, keeping two vectors only serve for the purpose of recovering `pre[i]`, which is simply `cur[i]` before its update. So we can use only one vector and the space is further optimized.\n\n    class Solution {\n    public:\n        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n            int m = obstacleGrid.size();\n            int n = obstacleGrid[0].size();\n            vector<int> cur(m, 0);\n            for (int i = 0; i < m; i++) {\n                if (!obstacleGrid[i][0])\n                    cur[i] = 1;\n                else break;\n            }\n            for (int j = 1; j < n; j++) {\n                bool flag = false;\n                if (obstacleGrid[0][j])\n                    cur[0] = 0;\n                else flag = true;\n                for (int i = 1; i < m; i++) {\n                    if (!obstacleGrid[i][j]) {\n                        cur[i] += cur[i - 1]; \n                        if (cur[i]) flag = true;\n                    }\n                    else cur[i] = 0; \n                }\n                if (!flag) return 0;\n            }\n            return cur[m - 1];\n        }\n    };
['Dynamic Programming', 'C++']