pic

Triangle 

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.

分析

题目的意思是，给定一个包含数字数组的三角形，找出自顶向下所有路径的最小和，每一行的数字只能和下一行相邻的两个数字移动。

         * 典型的DP问题
         * 可以看到每个数字triangle[i][j]在下一行都有两个相邻数字triangle[i+1][j]和triangle[i+1][j+1]
         * 借助于修改输入的triangle作为存储容器，自底向上，更新所有位置的minimumTotal
         * 每个位置的minimumTotal应该是原来元素triangle[i][j]的值加上min(triangle[i+1][j],triangle[i+1][j+1])
         * 新的triangle[0][0]就是要求的结果

Code

class Solution {
    public:
        /* 
         * 典型的DP问题
         * 可以看到每个数字triangle[i][j]在下一行都有两个相邻数字triangle[i+1][j]和triangle[i+1][j+1]
         * 借助于修改输入的triangle作为存储容器，自底向上，更新所有位置的minimumTotal
         * 每个位置的minimumTotal应该是原来元素triangle[i][j]的值加上min(triangle[i+1][j],triangle[i+1][j+1])
         * 新的triangle[0][0]就是要求的结果
         * */
        int minimumTotal(vector<vector<int> > &triangle) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(triangle.size() == 0)    return 0;
            for(int row = triangle.size() - 2; row >=0; row--)
            {
                for(int col = 0; col < triangle[row].size(); col++)
                {
                    //更新minimum值
                    triangle[row][col] += std::min(triangle[row+1][col], triangle[row+1][col+1]); 
                }
            }
            return triangle[0][0];
        }
};

pic