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.

C++:
01 int minPathSum(vector<vector<int> > &grid)
02 {
03     int n=grid.size();
04     if(n==0)
05         return 0;
06     int m=grid[0].size();
07     if(m==0)
08         return 0;
09     int A[n][m];
10     A[n1][m1]=grid[n1][m1];
11     for(int i=m2;i>=0;i)
12         A[n1][i]=grid[n1][i]+A[n1][i+1];
13     for(int i=n2;i>=0;i)
14         A[i][m1]=grid[i][m1]+A[i+1][m1];
15     for(int i=n2;i>=0;i){
16         for(int j=m2;j>=0;j){
17            int t=A[i+1][j]<A[i][j+1]?A[i+1][j]:A[i][j+1];
18            A[i][j]=t+grid[i][j];
19         }
20     }
21     return A[0][0];
22 }
Advertisements
This entry was posted in Array and linked list, Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s