原题
思路：
dp，从下往上依次取得最小的，取到最上面的，就是一条最小的路径。
class Solution
{
public:
int minimumTotal(vector<vector<int>> &triangle)
{
int rowSize = triangle.size();
int colSize;
if (rowSize == 0)
return -1;
if (rowSize == 1)
return triangle[0][0];
for (int row = rowSize - 2; row >= 0; row--)
{
colSize = triangle[row].size();
for (int col = 0; col < colSize; col++)
{
triangle[row][col] +=
min(triangle[row + 1][col], triangle[row + 1][col + 1]);
}
}
return triangle[0][0];
}
};
网友评论