LeetCode Minimum Path Sum algorithm

Question

I am attempting to solve the Minimum Path Sum algorithm problem and I have a working solution, however there was an unwritten requirement that the algorithm not exceed an unspecified amount of time for any given matrix of size (m x n).

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

I know that this is one of these problems perfectly suited to Dynamic Programming, however my brain turns to mush when I start reading up on it. This is supposed to be possible with two different state arrays capturing sums, but I am not comprehending how to do this accurate such that I am sure I am going the right direction.

public class Solution { int width = 0; int height = 0; HashMap<Point, Integer> previousStates = new HashMap<Point, Integer>(); public int minPathSum(int[][] grid) { previousStates = new HashMap<Point, Integer>(); height = grid.length; width = grid[0].length; return func(grid, new Point(0, 0)); } int func(int[][] grid, Point p) { if (p.x == (width - 1) && p.y == (height - 1)) { return grid[p.y][p.x]; } Point rightMostPoint = new Point(p.x + 1, p.y); Point downMostPoint = new Point(p.x, p.y + 1); boolean existingRightPreviousState = previousStates.containsKey(rightMostPoint); boolean existingDownPreviousState = previousStates.containsKey(downMostPoint); int rightLowestCost = (existingRightPreviousState) ? previousStates.get(rightMostPoint) : Integer.MAX_VALUE; int downLowestCost = (existingDownPreviousState) ? previousStates.get(downMostPoint) : Integer.MAX_VALUE; if (rightMostPoint.x < width && !existingRightPreviousState) { rightLowestCost = func(grid, rightMostPoint) + grid[p.y][p.x]; previousStates.put(rightMostPoint, rightLowestCost); } if (downMostPoint.y < height && !existingDownPreviousState) { downLowestCost = func(grid, downMostPoint) + grid[p.y][p.x]; previousStates.put(downMostPoint, downLowestCost); } return (rightLowestCost <= downLowestCost) ? rightLowestCost : downLowestCost; } } class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } public boolean equals(Object obj) { if (obj == null || !(obj instanceof Point)) return false; Point p = (Point)obj; return this.x == p.x && this.y == p.y; } public int hashCode() { return this.x ^ this.y; } } 

I start at the top left and recursively work either down or right based on which one returns the lowest sum. For a given cell in the matrix if I have already encountered it then I already know which Point has the lowest cost in relation to that so I don't have to re-evaluate it. In a way I am capturing state and using it but it still doesn't seem to meet the performance requirements of this problem. I am guessing the unspoken requirement is \$O(n)\$ complexity and I am unsure in my recursive approach if that is possible.

Do you have any suggestions for improvement here so that I can reduce the operational complexity of this algorithm or at least offer me a better explanation of how dynamic programming can be used to solve this?

Answer 1

Your approach is technically correct, but very complex. Your call stack gets very big and you use very much memory by creating two objects for each point. But you don't need to.

What are you doing with your recursive calls? You go go from start to end and put every point on the call stack. But you have every point in the matrix. You don't need to create a copy.

You do a depth first search, but you should do a breadth first search. Think about how you can manipulate the grid on the way down, so the solution could be found in the grid.

Answer 2

1. I think that your function will call itself that make things more complicated.
2. Is data structure "point" necessary in solving this problem?

Hope you can get some idea from my c++ solution.

 int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m,vector<int>(n,0)); //another m*n array dp[0][0] = grid[0][0]; for(int i = 1; i < n; i++) dp[0][i] = grid[0][i] + dp[0][i-1]; for(int j = 1; j < m; j++) dp[j][0] = grid[j][0] + dp[j-1][0]; for(int i = 1; i < n; i++) for(int j = 1; j < m; j++) dp[j][i] = grid[j][i] + min(dp[j-1][i],dp[j][i-1]); return dp[m-1][n-1]; }