leetcode 120.三角形最小路径和

从上到下，将结点的值原地改写为顶点到达该点的最小路径和，在上一层结点最小路径和已确定的情况下，两边的点只有一种可能路径，其它点只有两种可能路径。

int minimumTotal(vector<vector<int>> &triangle)
	{
		int row = triangle.size();
		if (row == 0)
		{
			return 0;
		}
		for (int n = 2; n <= row; n++)
		{
			for (int m = 1; m <= n; m++)
			{
				if (m == 1)
				{
					triangle[n - 1][m - 1] += triangle[n - 2][m - 1];
				}
				else if (m == n)
				{
					triangle[n - 1][m - 1] += triangle[n - 2][m - 2];
				}
				else
				{
					triangle[n - 1][m - 1] += triangle[n - 2][m - 1] <= triangle[n - 2][m - 2] ? triangle[n - 2][m - 1] : triangle[n - 2][m - 2];
				}
			}
		}
		int result = INT_MAX;
		for (auto &x : triangle[row - 1])
		{
			if (result > x)
			{
				result = x;
			}
		}
		return result;
	}