Clear and simple solution, time O(mn), space O(n), compared with UniquePath


  • 0
    P

    Compared to UniquePath, we can get some clues. I don't want to judge n or m who is smaller to save space. I just want to make the solutions as simple and clear as possible.

    1  1  1  1  1  1  1
       |  |  |  |  |  |
    1--2--3--4--5--6--7
       |  |  |  |  |  |
    1--3--6--10-15-21-28
    

    UniquePath

    cur[0] = 1 is the start palce.

    class Solution {
    public:
        int uniquePaths(int m, int n) {
            int i = 0, j = 0;
            vector<int> cur(n, 0);
            cur[0] = 1;
            for(i = 0; i < m; i++){
                for(j = 1; j < n; j++)
                    cur[j] += cur[j - 1];
            }
            return cur[n - 1];
        }
    };
    

    UniquePath II

    We need to judge whether the start point and end point is valid. We also need to judge obstacleGrid[i][0], so j should starts at 0.

    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            int i = 0, j = 0, m = obstacleGrid.size();
            if(m == 0) return 0;
            int n = obstacleGrid[0].size();
            vector<int> cur(n, 0);
            if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
                return 0;
            cur[0] = 1;
            for(i = 0; i < m; i++){
                for(j = 0; j < n; j++){
                    if(obstacleGrid[i][j] == 1)
                        cur[j] = 0;
                    else if(j > 0)
                        cur[j] += cur[j - 1];
                }
            }
            return cur[n - 1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.