三角形数组找最小和

形如:
[
[1],
[2,3],
[4,5,6],
[7,8,9,10]
]
的三角形数组，求从自上而下的路径累加和中最小的数，如上例就是1->2->4->7 == 14，只能上下相邻的数相加

动态规划，自顶向下分析，自底向上计算

int getMinSum(vector<vector<int>> triangle)
{
  if(triangle.size() == 0)
    return 0;
  int rows = triangle.size();
  vector<vector<int>> minsum(rows);
  for(int j = 0; j <rows; ++j)
    {
      vector<int> temp(j+1);
      minsum.push_back(temp);
    }

  // 初始化最低一层
  for(int j = 0; j<rows; j++)
    minsum[rows-1][j] = triangle[rows-1][j];
  // 自底向上保存最小值
  for(int row = rows-2; row>=0; --row)
    for(int col = 0; col<minsum[row].size(); ++col)
      {
        int min = minsum[row+1][col]<minsum[row+1][col+1]?
                  minsum[row+1][col]:minsum[row+1][col+1];
        minsum[row][col] = min + triangle[row][col];
      }
    return minsum[0][0];
}