Triangle

http://oj.leetcode.com/problems/triangle/

The problem statement is deceptive by mentioning path from “top” to “bottom”. I was fooled at first and tried to compare all the ways from the top to the bottoms. However, it is impractical since there are O(2^(n-1)) such paths.
I think this is a typical demonstration of the difference between bottom-up and top-down dynamic programming. It would be remarkably easier if we start from bottom and do upward. The solution is very short when the idea is set.

class Solution{
public:
    int minimumTotal(vector<vector<int>>& triangle ){		
		int N = triangle.size();
		if(!N)
			return 0;
		vector<int> r = triangle[N-1];
		for(int i= N-2; i>=0; i--){
			for(int j=0; j<=i; j++){
				r[j] = triangle[i][j]+min(r[j],r[j+1]);
			}
		}		
		return r[0];
	}
};
Advertisements
This entry was posted in Computer Science, LeetCode and tagged , , , . 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