LeetCode| Triangle 三角矩阵的最小路径和

给定一个三角矩阵 从最上层到最下层的距离最小，下层选择的数和上层选择的数必须是相邻的

思路：

这是一个典型的DP问题，如果设定dp[i][j]表示从最上层到当前元素的路径的最小值，那么到矩阵都被设置后，从最后一层中找到最小的即可。

只不过需要注意的是每一层的第一个元素和最后一个元素，因为这两个位置的相邻元素只有一个。初始化dp[0][0]为三角矩阵的第一个元素的值。

int Path(vector<vector<int> >& triangle)
{
	vector<vector<int> > dp(triangle.size());
	int i,j;
	int tmp;
	int min;
	for(i=0;i<triangle.size();i++)
		dp[i].assign(triangle.size(),100000);
	dp[0][0] = triangle[0][0];
	for(i=1;i<triangle.size();i++)
		for(j=0;j<=i;j++)
		{
			if(j ==0)
			{
				dp[i][j] = dp[i][j] < dp[i-1][j] + triangle[i][j]? dp[i][j]:dp[i-1][j] + triangle[i][j];
			}
			else if(j ==i)
			{
				dp[i][j] = dp[i][j] < dp[i-1][j-1]+triangle[i][j] ? dp[i][j]:dp[i-1][j-1] + triangle[i][j];
			}
			else
			{
				tmp = (dp[i-1][j-1]+triangle[i][j]	) < (dp[i-1][j]+triangle[i][j]) ? (dp[i-1][j-1]+triangle[i][j]):(dp[i-1][j]+triangle[i][j]);
				dp[i][j] = dp[i][j] < tmp ? dp[i][j]:tmp;
			}
			
		}
 
	tmp = triangle.size()-1;
	min = dp[tmp][0];
	for(i=0;i<tmp;i++)
		if(dp[tmp][i]<min)
			min = dp[tmp][i];
	return min;
	
}

int main()
{
	vector<vector<int> > triangle(4);
	int i,j;
	srand(rand()%100000);
	for(i=1;i<=4;i++)
		triangle[i-1].assign(i,0);
	
	for(i=0;i<triangle.size();i++)
		for(j=0;j<i+1;j++)
			triangle[i][j] = rand()%20; 

/*
	 triangle[0][0]=2;
	 triangle[1][0]=3;
	 triangle[1][1]=4;
	 triangle[2][0]=6;
	 triangle[2][1]=5;
	 triangle[2][2]=7;
	 triangle[3][0]=4;
	 triangle[3][1]=1;
	 triangle[3][2]=8;
	 triangle[3][3]=3; 
*/
	for(i=0;i<triangle.size();i++)
	{
		for(j=0;j<i+1;j++)
			cout<<triangle[i][j]<<" ";
		cout<<endl;
	}
	cout<<"+++++++"<<endl;
	cout<<Path(triangle)<<endl;	
	return 0;
}

LeetCode| Triangle 三角矩阵的最小路径和

原文：http://blog.csdn.net/yusiguyuan/article/details/44625947