首页 > 代码库 > leetcode 之 Triangle

leetcode 之 Triangle

2024-07-21 16:57:46   212人阅读

Triangle


Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

分析：本题是典型的动态规划，但是需要实现题目要求的空间复杂度是O(n)时，就需要重复利用空间了，由于动态规划的状态转移方程是只用到了相邻两行的数据，即dp[i][j] = min{dp[i-1][j],dp[i-1][j-1]}+triangle[i][j]，所以以前的数据不需要保存，从而达到重复利用的效果。


class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle)
    {
    	int rows = triangle.size();//该三角形的行和最大列是相等的，所用的空间复杂度即O(rows)
    	if(rows <= 0)return 0;
    	vector<int> dp(rows,0);
    	dp[0] = triangle[0][0];
    	int i,j;
    	for (i = 1;i < rows;i++)
    	{
    		for (j = triangle[i].size() - 1;j >= 0;--j)
    		{
    			if(j == 0)dp[j] = dp[j] + triangle[i][j];//第一列元素
    			else if(j == triangle[i].size()-1) dp[j] = dp[j-1] + triangle[i][j];//最后一列元素
    			else dp[j] = min(dp[j-1],dp[j]) + triangle[i][j];//中间的元素。
    		}
    	}
    	int res = dp[0];
    	for(i = 1;i < rows;i++)
    	{
    		if(dp[i] < res)res = dp[i];
    	}
    	return res;
    }
};

 

leetcode 之 Triangle


联系
我们