class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if (!triangle.size() || !triangle[0].size()) return 0; int rows = triangle.size(); int *ra = new int[rows]; int *rb = new int[rows]; int *tmp= NULL; int L, R; ra[0] = triangle[0][0]; for (int i=1; i<rows; i++) { vector<int>& row = triangle[i]; for (int j=0; j<=i; j++) { L = (j - 1) >= 0 ? ra[j-1] : INT_MAX; R = (j != i) ? ra[j] : INT_MAX; rb[j] = ((L < R) ? L : R) + row[j]; } tmp = ra, ra = rb, rb = tmp; } int sum = INT_MAX; for (int i=0; i<rows; i++) { if (ra[i] < sum) sum = ra[i]; } delete[] ra; delete[] rb; return sum; } };
这里使用了两个数组,如果入参允许改变的话可以直接在其上进行修改而不用其他额外空间,提交了一下也是可以。
LeetCode Triangle,布布扣,bubuko.com
原文:http://www.cnblogs.com/lailailai/p/3615032.html