When I looked at this question, the first thought was the Dijkstra solution, which is a very fast algorithm to calculate the shortest path. But this solution got TLE in this question, while DP solution worked fine.

I will talk about the Dijkstra solution first, as it's the first though came into my mind, and there is already discussions on the DP solution. If you are not interested in the Dijkstra solution, you can jump to the latter part of this post, which is about the DP solution, which is accepted.

**Dijkstra**

The idea of Dijkstra algorithm is to divide the graph into 2 parts, visited and unvisited.

For every node in the visited part has a *dist* value. Then we need to exam every edges across the visited part and the unvisited parts, which are edges that its start node is in the visited part, while its end node is in the unvisited part. What we are looking for is one edge, which has the minimum value of (dist(start node) + the edge's value). Then we put this node into the visited part and exam the edges again.

Following is the code. It uses a Java Heap, PriorityQueue to keep track of the minimum (dist(start node) + the edge's value), but in this question, the edge value is in the node itself, which is the same for every edges ending to it, so actually the heap just keeps track of the mimimum dist(start node) of every unvisited nodes around the boarder between visited and unvisited.

```
public class Solution_dijkstra {
class PointComparator implements Comparator<int[]>{
int[][] dist;
public PointComparator(int[][] dist){
this.dist = dist;
}
@Override
public int compare(int[] o1, int[] o2) {
int[] point1 = (int[])o1;
int[] point2 = (int[])o2;
return Integer.valueOf(dist[point1[0]][point1[1]])
.compareTo(Integer.valueOf(dist[point2[0]][point2[1]]));
}
}
public int minPathSum(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int[][] dist = new int[m][n];
for(int x = 0; x < m; x++){
for(int y = 0; y < n; y++){
dist[x][y] = Integer.MAX_VALUE;
}
}
dist[0][0] = grid[0][0];
PriorityQueue<int[]> pq = new PriorityQueue<int[]>( m*n, new PointComparator(dist));
pq.add(new int[]{0, 0});
while(!pq.isEmpty()){
int[] point = pq.poll();
int x = point[0];
int y = point[1];
int d = dist[x][y];
if(x == n-1 && y == m-1){
return d;
}
visited[x][y] = true;
if((y+1 < n) && !visited[x][y+1]){
dist[x][y+1] = min(
dist[x][y+1],
d + grid[x][y+1]);
pq.add(new int[]{x, y+1});
}
if((x+1 < m ) && !visited[x+1][y]){
dist[x+1][y] = min(
dist[x+1][y],
d + grid[x+1][y]);
pq.add(new int[]{x+1, y});
}
}
return 0;
}
private int min(int i1, int i2){
return i1 < i2 ? i1 : i2;
}
```

}

This solution got LTE error, mostly because of the priority queue and doesn't consider the special condition here that it's a grid and directed, which means a node can only be accessed from it's left and upper nodes. Put all these into consideration, we have the DP solution. It's essentially formula is

dist(node) = min( dist(upper node), dist(left node)) + node's value

**DP**

here is the code:

```
public class Solution_dp {
private int getDist(int[][] dist, int x, int y){
if(x < 0 || y < 0){
return Integer.MAX_VALUE;
}
return dist[x][y];
}
private int min(int i1, int i2){
return i1 < i2 ? i1 : i2;
}
public int minPathSum(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
int m = grid.length;
int n = grid[0].length;
int[][] dist = new int[m][n];
for(int x = 0; x < m; x++){
for(int y = 0; y < n; y++){
if(x == 0 && y == 0){
dist[0][0] = grid[0][0];
}else{
dist[x][y] = min(getDist(dist, x-1, y), getDist(dist, x, y-1)) + grid[x][y];
}
}
}
return dist[m-1][n-1];
}
```

}