recursive C# solution using memoization (DP)


  • 0
    K
    public class Solution {
        public int UniquePathsWithObstacles(int[,] obstacleGrid) {
            int m = obstacleGrid.GetLength(0);
            int n = obstacleGrid.GetLength(1);
            int[,] grid = new int[m,n];
            
            if (obstacleGrid[m-1,n-1] == 1) //unreachable bottom-right corner
                return 0;
            else 
                return NumPaths(m-1,n-1,obstacleGrid,grid);
        }
        public int NumPaths(int x,int y,int[,] obstacleGrid,int[,] grid) {
            if (x == 0 && y == 0)
                grid[x,y] =  1 - obstacleGrid[0,0];
            else {
                int up = 0;
                int next = 0;
                if (x > 0)
                    up = obstacleGrid[x-1,y] == 1 ? 0 : (grid[x-1,y] == 0 ? NumPaths(x-1,y,obstacleGrid,grid) : grid[x-1,y]);
                if (y > 0)
                    next = obstacleGrid[x,y-1] == 1 ? 0 : (grid[x,y-1] == 0 ? NumPaths(x,y-1,obstacleGrid,grid) : grid[x,y-1]);
                grid[x,y] = up + next;
            }
            return grid[x,y];
        }    
    }
    

Log in to reply
 

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