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).
給定一個(gè)三角形二元數(shù)組，求從頭節(jié)點(diǎn)到葉子結(jié)點(diǎn)的最短路徑。
動(dòng)態(tài)規(guī)劃洞就，將triangle[i][j]賦值為直到triangle[i][j]節(jié)點(diǎn)時(shí)的最短路徑長(zhǎng)度咏连，則可以分成三個(gè)部分考慮：
（1）ij在三角形最左側(cè)轴脐，則triangle[i][j] += triangle[i-1][j]
（2）ij在三角形最右側(cè)堪藐，則triangle[i][j] += triangle[i-1][j-1]
（3）ij在中間滋恬，則triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
class Solution {
public:
? int minimumTotal(vector<vector<int> > &triangle) {
? ? ? ? int n = triangle.size();
? ? ? ? //動(dòng)態(tài)規(guī)劃
? ? ? ? for(int i=1; i<n; i++){
? ? ? ? ? ? for(int j=0; j<triangle[i].size(); j++){
? ? ? ? ? ? ? ? if(j==0){
? ? ? ? ? ? ? ? ? ? triangle[i][j] += triangle[i-1][j];
? ? ? ? ? ? ? ? }else if(j == triangle[i].size()-1){
? ? ? ? ? ? ? ? ? ? triangle[i][j] += triangle[i-1][j-1];
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int res;
? ? ? ? if(n>0) res = triangle[n-1][0];
? ? ? ? for(int k=0; k<triangle[n-1].size(); k++){
? ? ? ? ? ? res = min(res, triangle[n-1][k]);
? ? ? ? }
? ? ? ? return res;
? }
};
