#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*問題: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, where n is the total number of rows in the triangle.分析：這是動態(tài)規(guī)劃問題。設(shè)dp[i]表示從根節(jié)點到當(dāng)前第i行時獲取的最大和dp[0]=底部的值是確定的，那么我們可以自底向上來做，設(shè)當(dāng)前數(shù)為A[i][j]，那么A[i][j]只可能從A[i+1][j]或者A[i+1][j+1]中選擇下一個要遍歷的元素設(shè)dp[i][j]表示從元素A[i][j]到達(dá)最下一面一層的時候的所有和的最小值dp[i][j] = min(dp[i+1][j] , dp[i+1][j+1]) + A[i][j]假設(shè)總共有row行dp[row-1][j] = A[i][j],所求結(jié)果就是dp[0][0]輸入:4(行數(shù))1(當(dāng)前行中元素個數(shù)) 22 3 436 5 744 1 8 3輸出:11關(guān)鍵:1 dp[i]表示莫一行第i個元素到最底部的和的最小值用動態(tài)規(guī)劃，進(jìn)行遞推，從最下面一行開始，當(dāng)前行和下面行的對應(yīng)兩個數(shù)的結(jié)果，并提供給上一行使用即可。for(int i = row - 2; i >= 0 ; i--){	len = triangle.at(i).size();	//最后一個元素要取到	for(int j = 1 ; j <= len ; j++)	{		//更新當(dāng)前行，當(dāng)前行的元素，是該元素到底部的最短距離		dp.at(j-1) = min( dp.at(j-1) , dp.at(j)) + triangle.at(i).at(j-1);	}}*/class Solution {public:    int minimumTotal(vector<vector<int>>& triangle) {        if(triangle.empty())		{			return 0;		}		int row = triangle.size();		//由于是三角形，最大列數(shù)在最后一行		int col = triangle.at(row - 1).size();		vector< int > dp( col , 0 );		int len = triangle.at(row - 1).size();		//初始化最下面一行的值		for(int i = 0 ; i < len ; i++)		{			dp.at(i) = triangle.at(row-1).at(i);		}		//用動態(tài)規(guī)劃，進(jìn)行遞推，從最下面一行開始，當(dāng)前行和下面行的對應(yīng)兩個數(shù)的結(jié)果，并提供給上一行使用即可		for(int i = row - 2; i >= 0 ; i--)		{			len = triangle.at(i).size();			//最后一個元素要取到			for(int j = 1 ; j <= len ; j++)			{				//更新當(dāng)前行，當(dāng)前行的元素，是該元素到底部的最短距離				dp.at(j-1) = min( dp.at(j-1) , dp.at(j)) + triangle.at(i).at(j-1);			}		}		return dp.at(0);    }};void PRocess(){	 vector<vector<int> > nums;	 int value;	 int row;	 int col;	 Solution solution;	 while(cin >> row )	 {		 nums.clear();		 for(int i = 0 ; i < row ; i++)		 {			 cin >> col;			 vector<int> datas;			 for(int j = 0 ; j < col ;j++)			 {				 cin >> value;				 datas.push_back(value);			 }			 nums.push_back(datas);		 }		 int result = solution.minimumTotal(nums);		 cout << result << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}