120. 三角形最小路徑和
摘要：
題目描述
給定一個三角形，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。
例如，給定三角形（用二維向量triangle表示）：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即，2 ...
題目描述
給定一個三角形，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。
例如，給定三角形（用二維向量triangle表示）：
[ [2], [3,4], [6,5,7], [4,1,8,3] ] 自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。
說明：
如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數）來解決這個問題，那麼你的演算法會很加分。
演算法
利用動態規劃求解自上向下的三角形路徑和，難點在於要求額外的空間複雜度位O(n)。那麼不妨利用傳入的二維向量作為一個媒介更新dp陣列。
如果沒有複雜度要求的話，可以開一個二維陣列dp[n][n]，n是三角形的行數。從上至下的更新情況下所示：
[ [2], [5,6], [11,10,13], [15,11,18,13] ]
最終返回的是dp的最後一行中最小的那個數。
現在要求空間複雜度為O(n)，即最多隻能開一個一維陣列dp[n]，n是三角形的行數。可以將dp中的數加到triangle中對應的行，最後再將triangle中對應的該行重新儲存回dp。一位triangle一行最多儲存n個數，所以dp[n]已經夠用。詳細註釋在程式碼中給出。
程式碼
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int size = triangle.size();
// 邊界條件，若triangle僅有一行，直接返回第一行的該數即可
if(size == 1)
return triangle[0][0];
// 開dp陣列
int dp[size];
dp[0] = triangle[0][0];
// 自三角形的第二行從上到下遍歷，體現在下標為i=1。因為二維向量由i=0開始，i=0代表第一行，這裡不要搞混了。
for (int i = 1; i < size; i++)
{
// 從前往後遍歷triangle[i]這個向量，並用已經儲存的dp陣列更新triangle[i]
for (int j = 0; j <= i; j++)
{
if(j == 0)
triangle[i][j] += dp[j];
else if(j == i)
triangle[i][j] += dp[j-1];
else
triangle[i][j] += min(dp[j], dp[j-1]);
}
// 重新儲存回dp陣列，以用來更新三角形的下一行
for (int j = 0; j < triangle[i].size(); j++)
dp[j] = triangle[i][j];
}
// 取dp中最小的那個數返回
int _min = 99999999;
for (int j = 0; j < size; j++)
if(_min > dp[j])
_min = dp[j];
return _min;
}
};