So I was solving this problem on LeetCode. This is my AC code in Java. After this I tried solving a similar problem on the CodeStudio platform which was this. As you can see, this problem is very much similar to the LC problem with the only difference being the direction in which we can move and the fact that the ending index , instead of being the bottom right cell, can be any cell in the bottom row. So, in the LC problem my code was getting terminated whenever the current x & y coordinates of the cell became equal to the coordinates of the bottom right cell.
Now to solve the CodeStudio problem, what I tried doing was, since the end index can be any cell in the last row , I ran a loop from i = 0 to i = n-1 and kept finding out the min value possible from [0][0] to [n-1][i]. I check for every cell in the last row and return the minimum value whatever it may be as you can see in this code. (ignore the compilation errors since I am not writing the Main class.) However this code gave correct output for only 9/11 test cases and gives wrong answer for the other two. So it would be of great help to me if anybody can point out the error in my logic as to why those 2 TCs fail . Thank you
There are two problems in your code.
The first one, for minPathSum, has a complexity is n^2. You call this function once for each endpoint value when calculating the answer. So the total time is n^3, which would be difficult to pass for n=1000.
The second one, In the Leetcode problem it satisfies that the weights must be positive, so using the priority queue does not present a problem. In another problem there may be negative weights, which means that the answer at a point may be refreshed at any time, so you cannot use visited, which will keep only the first calculated answer. You can set the priority of the coordinates in the priority queue over the priority of the values, or just use recursive dp.