先來看看例題：
Leetcode120題： 三角形最小路徑和
給定一個(gè)三角形约巷，找出自頂向下的最小路徑和偎痛。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。
示例數(shù)組
自頂向下的最小路徑和為 11（即踩麦，2 + 3 + 5 + 1 = 11）。
第一種方法：也是最直觀的方法氓癌，首先谓谦，創(chuàng)建一個(gè)和原來數(shù)組相等大小的數(shù)組空間tmp，然后遍歷每一個(gè)節(jié)點(diǎn)去更新tmp的值贪婉，更新后的tmp反粥，最后，所希望獲取的返回值即為最后一行的最小值疲迂。此方法很容易理解星压，但空間消耗略打，話不多說看代碼：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.empty()) return 0;
vector<vector<int>> tmp(triangle);
for(int i=1;i<triangle.size();i++){
for(int j=0;j<triangle[i].size();j++){
if(j==triangle[i].size()-1) tmp[i][j] = tmp[i-1][j-1]+triangle[i][j];
else if(j==0) tmp[i][j] = tmp[i-1][j]+triangle[i][j];
else{
tmp[i][j] = min(tmp[i-1][j],tmp[i-1][j-1])+triangle[i][j];
}
}
}
int temp = tmp[tmp.size()-1][0];
for(int i=0;i<tmp[tmp.size()-1].size();i++){
if (temp>tmp[tmp.size()-1][i])
temp = tmp[tmp.size()-1][i];
}
return temp;
}
};
第二種方法：
圖片
在上一步的遍歷過程當(dāng)中鬼譬，我們可以看到 在遍歷第k行的時(shí)候娜膘，只和第k-1行有關(guān)，與再之前的數(shù)不會(huì)再次使用优质，因而竣贪，對(duì)代碼進(jìn)行優(yōu)化军洼，只需要nums最后一行的個(gè)數(shù)的額外空間即可，代碼如下：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.empty()) return 0;
vector<int> tmp(triangle.size(),0);
for(int i=0;i<triangle.size();i++){
for(int j=triangle[i].size()-1;j>=0;j--){
if(j==0) tmp[j] = triangle[i][j] + tmp[j];
else if(j == triangle[i].size()-1) tmp[j] = triangle[i][j] + tmp[j-1];
else{
tmp[j] = triangle[i][j] + min(tmp[j],tmp[j-1]);
}
}
}
int temp = tmp[0];
for(int i = 0; i<tmp.size();i++){
if(tmp[i]<temp) temp = tmp[i];
}
return temp;
}
};
我們?cè)谄浠A(chǔ)上進(jìn)行優(yōu)化演怎，從下而上分析會(huì)略簡化代碼匕争，無需else if/else：
然后就得到了非常優(yōu)雅的代碼：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> tmp(triangle[triangle.size()-1]);
for(int i=triangle.size()-2;i>=0;i--){
for(int j=0;j<triangle[i].size();j++){
tmp[j] = triangle[i][j] + min(tmp[j],tmp[j+1]);
}
}
return tmp[0];
}
};
提交結(jié)果：
提交結(jié)果展示
