c# O(n) space


  • 0
    N
    public class Solution {
        public int MinPathSum(int[,] grid)
        {
            if (grid == null || grid.GetLength(0) == 0) return 0;
            var m = grid.GetLength(0);
            var n = grid.GetLength(1);
    
            var res = new int[n];
            var sum = 0;
            for (var i = 0; i < n; i++)
            {
                sum += grid[0, i]; // be careful about init with sum not only value of each element.
                res[i] = sum ;
            }
    
            for (var i = 1; i < m; ++i)
            {
                res[0] = res[0] + grid[i, 0];
                for (var j = 1; j < n; ++j)
                {
                    res[j] = Math.Min(res[j], res[j - 1]) + grid[i, j];
                }
            }
    
            return res[n - 1];
        }
    }
    

Log in to reply
 

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