A 9-Line C# DP Solution


  • 0
    L
    public int UniquePathsWithObstacles(int[,] obstacleGrid) {
        int m = obstacleGrid.GetLength(0), n = obstacleGrid.GetLength(1);
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(obstacleGrid[i, j] == 0){
                    int up = i == 0 ? 0 : obstacleGrid[i - 1, j] < 0 ? 0 : obstacleGrid[i - 1, j];
                    int left = j == 0 ? 0 : obstacleGrid[i, j - 1] < 0 ? 0 : obstacleGrid[i, j - 1];
                    obstacleGrid[i, j] = i != 0 || j != 0 ? up + left : 1;
                }else obstacleGrid[i, j] = -1;
        return obstacleGrid[m - 1, n - 1] < 0 ? 0 : obstacleGrid[m - 1, n - 1];
    }

  • 0

    Hint: This can be improved quite a bit... the three longest lines can be much shorter.


  • 0
    L

    Thanks for the heuristic, Stefan.

    public int UniquePathsWithObstacles(int[,] obstacleGrid) {
        int m = obstacleGrid.GetLength(0), n = obstacleGrid.GetLength(1);
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(obstacleGrid[i, j] == 0){
                    int up = i == 0 ? 0 : obstacleGrid[i - 1, j];
                    int left = j == 0 ? 0 : obstacleGrid[i, j - 1];
                    obstacleGrid[i, j] = i != 0 || j != 0 ? up + left : 1;
                }else obstacleGrid[i, j] = 0;
        return obstacleGrid[m - 1, n - 1];
    }

  • 0

    Glad the hint worked :-). You can shorten the return-line as well, btw.


  • 0
    L

    Yes. Thanks.


Log in to reply
 

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