# LeetCode题目：Minimum Path Sum，A*算法

By | 2012 年 10 月 16 日

Minimum Path Sum
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.

```struct Point {
int row;
int col;
int dist;
bool rightVisited,downVisited;
Point(int r,int c,int d = 0):row(r),col(c),dist(d),rightVisited(false),downVisited(false) {;}
Point():row(0),col(0),dist(0),rightVisited(false),downVisited(false) {;}
void print(){
cout<<"r"<";
}
};

class Solution {
public:
int minPathSum(vector > &grid) {
// Using Dijkstra algorithm
const int veryLarge = 1000000;
int rows = grid.size();
if (rows == 0) return 0;
int cols = grid[0].size();
if (cols == 0) return 0;
list starters;
Point startPt(0,0,grid[0][0]);
if(startPt.col == cols - 1 && startPt.row == rows - 1) return startPt.dist;
//startPt.print();
starters.push_back(startPt);
while(starters.size()){
list::iterator minStarterIt;
bool rightMin;
int minNextStep = veryLarge;
for(list::iterator it = starters.begin(); it != starters.end(); ++ it) {
Point &pt = *it;

bool haveRight = pt.col + 1 < cols && !pt.rightVisited;
int right = (haveRight ? grid[pt.row][pt.col + 1] + pt.dist : veryLarge);
if(!haveRight) pt.rightVisited = true;

bool haveDown = pt.row + 1 < rows && !pt.downVisited;
int down = (haveDown ? grid[pt.row + 1][pt.col] + pt.dist : veryLarge);
if(!haveDown) pt.downVisited = true;

if (haveRight && right < minNextStep) {
minStarterIt = it;
minNextStep = right;
rightMin = true;
}
if (haveDown && down < minNextStep) {
minStarterIt = it;
minNextStep = down;
rightMin = false;
}
}
Point &minPt = *minStarterIt;
//minPt.print();
Point nextStep(minPt.row,minPt.col);
nextStep.rightVisited = false;
nextStep.downVisited = false;
nextStep.dist = minNextStep;
if(rightMin) {
nextStep.col += 1;
minPt.rightVisited = true;
} else {
nextStep.row += 1;
minPt.downVisited = true;
}
//nextStep.print();
if (nextStep.row == rows - 1 && nextStep.col == cols - 1) {
return nextStep.dist;
} else {
if(minPt.rightVisited && minPt.downVisited){
//remove from starters
starters.erase(minStarterIt);
}
starters.push_back(nextStep);
}
}
return veryLarge;
}
};
```

Code rewrite at 2013-2-5,60 ms pass large set.
Time complexity = O(rows * cols)
Space complexity = O(rows), Can optimized to min(rows,cols)

```class Solution {
public:
int minPathSum(vector > &grid) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = grid.size();
if(0 == rows) return 0;
int cols = grid[0].size();
if(0 == cols) return 0;
//the min path sum at each colum
int *pathsum = new int[rows];
int *pathsumtemp = new int [rows];
//initilazing the first colum
for(int ir = 0; ir < rows; ++ir) {
pathsum[ir] = grid[ir][0];
if(ir>0) {
pathsum[ir] += pathsum[ir-1];
}
}
//calculate the rest of grid
for(int ic = 1; ic < cols; ++ic) {
//caculate the pathsum for colum ic into pathsumtemp
pathsumtemp[0] = pathsum[0] + grid[0][ic];
for(int ir = 1; ir < rows; ++ir) {
int dist = pathsum[ir];//from left
if(dist > pathsumtemp[ir-1])
dist = pathsumtemp[ir-1];//from top
pathsumtemp[ir] = dist + grid[ir][ic];
}
//swap the pointer of pathsum and pathsumtemp
int *temp = pathsum;
pathsum = pathsumtemp;
pathsumtemp = temp;
}
//return the last element in the pathsum
int ret = pathsum[rows-1];
delete pathsum;
delete pathsumtemp;
return ret;
}
};
```

## 4 thoughts on “LeetCode题目：Minimum Path Sum，A*算法”

1. charles
```class Solution {
public:
int minPathSum(vector<vector>& grid) {
for(int r=0;r<(int)grid.size();r++)
for(int c=(0==r?1:0);c<(int)grid[r].size();c++)
0==r?grid[r][c]+=grid[r][c-1]:(0==c?grid[r][c]+=grid[r-1][c]:grid[r][c]+=min(grid[r-1][c],grid[r][c-1]));
return grid[(int)grid.size()-1][(int)grid[0].size()-1];
}
};```