LeetCode| 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, wheren is the total number of rows in the triangle.

給定一個三角矩陣 從最上層到最下層的距離最小，下層選擇的數和上層選擇的數必須是相鄰的

思路：

這是一個典型的DP問題，如果設定dp[i][j]表示從最上層到當前元素的路徑的最小值，那麼到矩陣都被設置後，從最後一層中找到最小的即可。

只不過需要注意的是每一層的第一個元素和最後一個元素，因為這兩個位置的相鄰元素只有一個。初始化dp[0][0]為三角矩陣的第一個元素的值。

 

int Path(vector >& triangle)
{
	vector > dp(triangle.size());
	int i,j;
	int tmp;
	int min;
	for(i=0;i > triangle(4);
	int i,j;
	srand(rand()%100000);
	for(i=1;i<=4;i++)
		triangle[i-1].assign(i,0);
	
	for(i=0;i