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 class Solution {
02 public:
03     int minPathSum(vector<vector<int> > &grid) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int m=grid.size();
07         if(m==0)
08             return 0;
09         int n=grid[0].size();
10         vector<int*> A(m);
11         for(int i=0;i<m;i++)
12         {
13             A[i]=new int[n];
14             for(int j=0;j<n;j++)
15             {
16                 A[i][j]=0;
17             }
18         }
19         A[0][0]=grid[0][0];
20         for(int i=1;i<n;i++)
21         {
22             A[0][i]=A[0][i1]+grid[0][i];
23         }
24         for(int i=1;i<m;i++)
25         {
26             A[i][0]=A[i1][0]+grid[i][0];
27         }
28         for(int i=1;(i<n)&&(i<m);i++)
29         {
30             A[i][i]=A[i1][i]<A[i][i1]?
31               A[i1][i]+grid[i][i]:A[i][i1]+grid[i][i];
32             for(int j=1;i+j<n;j++)
33             {
34                 A[i][j+i]=A[i1][j+i]<A[i][j+i1]?
35                   A[i1][j+i]+grid[i][j+i]:A[i][j+i1]+grid[i][j+i];
36             }
37             for(int j=1;i+j<m;j++)
38             {
39                 A[i+j][i]=A[i+j][i1]<A[i+j1][i]?
40                   A[i+j][i1]+grid[i+j][i]:A[i+j1][i]+grid[i+j][i];
41             }
42         }
43         return A[m1][n1];
44     }
45 };
Advertisements
This entry was posted in 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