leetcode 120. 三角形最小路径和

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
相邻结点：与(i, j) 点相邻的结点为 (i + 1, j) 和 (i + 1, j + 1)。

class Solution {
public:
	int minimumTotal(vector<vector<int>>& triangle) {
		return dfs(triangle, 0, 0);
	}
	int dfs(vector<vector<int>>& triangle,int i,int j)
	{
		if (i == triangle.size()) return 0;
		return min(dfs(triangle, i + 1, j),dfs(triangle,i+1,j+1))+triangle[i][j];
	}
};

class Solution {
	map<pair<int, int>, int> map;
public:
	int minimumTotal(vector<vector<int>>& triangle) {
		return dfs(triangle, 0, 0);
	}
	int dfs(vector<vector<int>>& triangle,int i,int j)
	{
		if (i == triangle.size()) return 0;
		if (map.find({ i,j }) != map.end()) return map[{i, j}];
		return map[{i, j}]=min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1))+triangle[i][j];
	}
};

class Solution {
public:
	int minimumTotal(vector<vector<int>>& triangle) 
	{
		if (triangle.empty()) return 0;
		int r = triangle.size();//行
		vector<vector<int>> dp(triangle.size(), vector<int>(triangle[r-1].size()));
		//初始值
		dp[0][0] = triangle[0][0];
		//第一列
		for (int i = 1; i < r; i++)
			dp[i][0] = dp[i - 1][0] + triangle[i][0];
		for (int i = 1; i < r; ++i)
		{
			int j = 1;
			//注意计算的是三角形每一行的长度都不同
            //最后一列需要单独计算(斜边)，所以是从遍历的个数是size()-1
			while (j <triangle[i].size()-1)
			{
				//状态转移公式
				dp[i][j] = min(dp[i - 1][j - 1], dp[i-1][j])+triangle[i][j];
				++j;
			}
			//三角形斜边需要单独计算
			dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
		}
		//最后一行保存了每条路径的计算结果，对最后一行数组求min即为最终结果
		     int Min = INT_MAX;
			for (int j = 0; j <triangle[r-1].size(); j++)
			{
				Min = min(Min, dp[r-1][j]);
			}
			return Min;
	}
};

dp[i][j] = min(dp[i+1][j+1],dp[i+1][j]) + triangle[i][j]

class Solution {
public:
	int minimumTotal(vector<vector<int>>& triangle) 
	{
		if (triangle.empty()) return 0;
		int r = triangle.size();
		int c = triangle[r-1].size();//最后一行的长度
		vector<vector<int>> dp(r + 1, vector<int>(c + 1,0));
		//自下而上推导
		for (int i = r - 1; i >= 0; i--)
		{
			int j = triangle[i].size()-1;
			while (j >= 0)
			{
				//对于三角形的每一行，从右向左计算
				dp[i][j] = min(dp[i + 1][j + 1], dp[i + 1][j]) + triangle[i][j];
				--j;
			}
		}
		//最终结果就保存在第一行第一列中
		return dp[0][0];
	}
};

class Solution {
public:
	int minimumTotal(vector<vector<int>>& triangle) 
	{
		if (triangle.empty()) return 0;
		int r = triangle.size();
		int c = triangle[r-1].size();//最后一行的长度
		vector<int> dp(c + 1,0);
	    //自下而上推导
		for (int i = r - 1; i >= 0; i--)
		{
			//从左到右的方式计算
			for (int j = 0; j < triangle[i].size(); ++j)
			{
				dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
			}
		}
		//dp数组的第一个元素即为最终结果
		return dp[0];
	}
};