Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

C++:
01 class Solution {
02 public:
03     int minimumTotal(vector<vector<int> > &triangle) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int n=triangle.size();
07         if(n==0)
08             return 0;
09         vector<int> A(n);
10         vector<int> B(n);
11         A[0]=triangle[0][0];
12         for(int i=1;i<n;i++)
13         {
14            B[0]=A[0]+triangle[i][0];
15            B[i]=A[i1]+triangle[i][i];
16            for(int j=1;j<i;j++)
17            {
18                B[j]=A[j1]<A[j]?
19                  A[j1]+triangle[i][j]
20                  :A[j]+triangle[i][j];
21            }
22            vector<int> C=A;
23            A=B;
24            B=C;
25         }
26         int min=A[0];
27         for(int i=0;i<n;i++)
28         {
29             min=min<A[i]?min:A[i];
30         }
31         return min;
32     }
33 };
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