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
