首页 > 代码库 > LeetCode: Triangle

LeetCode: Triangle

2024-07-19 11:16:00   216人阅读

LeetCode: 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.

地址：https://oj.leetcode.com/problems/triangle/

算法：开两个大小为n的数组，假设我们已经完成了前面i行的搜索，其中以第i行第j个元素为终节点的最小路径的和存储在其中某个数组里，假设这个数组用指针pre指向。接下去，我们要完成第i+1行的搜索，其中以第i+1行第j个元素为终节点的路径必定是从第i行第j个节点或者第i行第j+1个节点下来的，所有在计算最小路径时只需考虑这两个路径，并把结果存储在另一个数组里，这个数组用指针p指向。由于在每一次搜索的过程中只需要上一次的结果，所以我们只用了两个数组，并且用指针pre和指针p来重复利用这两个数组，这样就可以达到O(n)的空间要求。代码：

 1 class Solution { 2 public: 3     int minimumTotal(vector<vector<int> > &triangle) { 4         int n = triangle.size(); 5         if(n < 1)    return 0; 6         if(n == 1)   return triangle[0][0]; 7         vector<int> min1(n); 8         vector<int> min2(n); 9         min1[0] = triangle[0][0];10         vector<int> *pre = &min1;11         vector<int> *p   = &min2;12         for(int i = 1; i < n; ++i){13             for(int j = 0; j <= i; ++j){14                 if(j == 0){15                     (*p)[j] = (*pre)[j] + triangle[i][j];16                 }else if(j == i){17                     (*p)[j] = (*pre)[j-1] + triangle[i][j];18                 }else{19                     (*p)[j] = ( (*pre)[j] > (*pre)[j-1] ? (*pre)[j-1] : (*pre)[j] ) + triangle[i][j];20                 }21             }22             vector<int> *t = pre;23             pre = p;24             p = t;25         }26         int result = (*pre)[0];27         for(int i = 1; i < n; ++i){28             if (result > (*pre)[i]) result = (*pre)[i];29         }30         return result;31     }32     33 };

 

LeetCode: Triangle


联系
我们