LeetCode120:三角形最小路径和

解析：

        一种比较浪费空间的方法是定义一个同样的二维数组，存储自上而下每一个位置的路径和，然后找到最后一行的最小值，就可以得出最后的结果。这种方法的缺点是比较浪费空间，但是方法简单易懂。但是要注意，每一行的第一个位置，只能从它直接上方计算得到，即：result[row][0] = result[row-1][0] + triangle[row][0]; 每一行的最后一个值，只能是其左上方的值计算得到，即：result[row][row] = result[row-1][row-1] + triangle[row][row]; 其他位置的值，计算方法为：                                                    result[row][col] = triangle[row][col] + min(result[row-1][col] , result[row-1][col-1])。

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minimumTotal(vector<vector<int>>& triangle) 
{
	if (triangle.empty())
		return 0;
	int rows = triangle.size();
	int colums = triangle[rows - 1].size();
	vector<vector<int>>result(rows, vector<int>(colums, 0));//结果数组
	result[0][0] = triangle[0][0];
	for (int i = 1; i < rows; i++)//计算1到最后一行
	{
		result[i][0] = result[i - 1][0] + triangle[i][0];
		for (int j = 1; j < i; j++)
		{
			result[i][j] = triangle[i][j] + min(result[i - 1][j], result[i - 1][j - 1]);
		}
		result[i][i] = triangle[i][i] + result[i - 1][i - 1];
	}
	int minPath = INT_MAX;//找最小值
	for (int i = 0; i < colums; i++)
	{
		if (result[rows - 1][i] < minPath)
			minPath = result[rows - 1][i];
	}
	return minPath;
}

 leetcode中还有给出不需要额外空间的方法，就是自底向上计算，直到最顶端，就找到了最小值。

    int minimumTotal(vector<vector<int>> & triangle)
    {
        for (int i = triangle.size() - 2; i >= 0; i--)
        for (int j = 0; j < triangle[i].size(); j++)
            triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        return triangle[0][0];
    }