EEPW论坛

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 is11(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.

题意：给定一个三角形，找到一条从顶部到底部的路径，要求路径上的和的值最小，每一步你只能往下一行的相邻位置走下去；这种典型的利用动态规划方式思考的；设f(i,j)是从第一行到第i行，第j个数字的最小和值，那么f(i,j)要么是f(i-1, j-1) 而来，要么是f(i-1, j)而来，因此最优子结构为f(i,j)=min(f(i-1, j-1), f(i-1, j))+triangle[i][j]


通过这种方式，可以得到从第一行到第n行的所有点的最小和值，然后
取第n行的最小值即可[cpp] view plain copy

1. class Solution  

2. {  

3. public:  

4.     int minimumTotal(vector<vector<int>> & triangle)  

5.     {  

6.         if (triangle.size()==0)  

7.         {  

8.             return 0;  

9.         }  

10.   

11.         vector<vector<int>> dp;  

12.         vector<int> vec;  

13.         vec.push_back(triangle[0][0]);  

14.   

15.         dp.push_back(vec);  

16.         vec.resize(0);  

17.   

18.         for (int i=1; i<triangle.size(); i++)  

19.         {  

20.             for (int j=0; j<triangle[i].size(); j++)  

21.             {  

22.                 if (j==0)  

23.                 {  

24.                     vec.push_back(triangle[i][0]);  

25.                 }  

26.                 else if(j==triangle[i].size()-1)  

27.                 {  

28.                     vec.push_back(triangle[i][j]+dp[i-1][j-1]);  

29.                 }  

30.                 else  

31.                 {  

32.                     vec.push_back(min(dp[i - 1][j - 1] + triangle[i][j], dp[i - 1][j] + triangle[i][j]));  

33.                 }  

34.             }  

35.   

36.             dp.push_back(vec);  

37.             vec.resize(0);  

38.         }  

39.   

40.         int last = dp.size() - 1;  

41.         int minpath = dp[last][0];  

42.         for (int i = 1; i<dp[last].size(); i++)  

43.             if (dp[last][i]<minpath)  

44.                 minpath = dp[last][i];  

45.   

46.         return minpath;  

47.     }  

48. };