recursive C# solution with memoization (DP)


  • 0
    K
    public class Solution {
        public int MinPathSum(int[,] grid) {
            int m = grid.GetLength(0);
            int n = grid.GetLength(1);
            int[,] sums = new int[m,n];
            return PathSum(m-1,n-1,grid,sums);
        }
        public int PathSum(int x,int y,int[,] grid,int[,] sums) {
            if (x == 0 && y == 0) 
                sums[x,y] = grid[x,y];
            else if (x == 0)
                sums[x,y] = grid[x,y] + PathSum(x,y-1,grid,sums);
            else if (y == 0)
                sums[x,y] = grid[x,y] + PathSum(x-1,y,grid,sums);   
            else
            {
                sums[x,y] = grid[x,y] + 
                            Math.Min(sums[x-1,y] == 0 ? PathSum(x-1,y,grid,sums) : sums[x-1,y] , 
                                     sums[x,y-1] == 0 ? PathSum(x,y-1,grid,sums) : sums[x,y-1]);
            }
            return sums[x,y];
        }
    }
    

Log in to reply
 

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