给定一个三角形,找到从上到下的最小路径总和。 您可以将每个步骤移动到下面一行中的相邻数字。 例如,给定以下三角形 [ [2], [3,4], [6,5,7], [4,1,8,3] ]] 从顶部到底部的最小路径总和为11(即,2 + 3 + 5 + 1 = 11)。 注意: 奖励点,如果你能够使用只使用O(n)额外的空间,其中n是三角形中的总行数。
//从上到下遍历 class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int row = triangle.size(); vector<vector<int> > path(row);//申请行空间,二维数组 for (int i=0; i<row; i++) path[i].resize(triangle[i].size(), 0);//申请列空间 //path[0][0] = triangle[0][0]; int col = 0; for (int i=0; i<row; i++){ col = triangle[i].size(); for (int j=0; j<col; j++){ if (0 == i) path[i][j] = triangle[i][j]; else{ if (j == 0) path[i][j] = path[i-1][j] + triangle[i][j]; else if (j == (col-1)) path[i][j] = path[i-1][j-1] + triangle[i][j]; else //当不是首尾数字的时候,看上一层相邻的两个数哪个更小更适合想加 path[i][j] = min(path[i-1][j-1], path[i-1][j]) + triangle[i][j]; } } } int Min = path[row-1][0]; for (int i=0 ;i<path[row-1].size(); i++) if (Min > path[row-1][i]) Min = path[row-1][i]; return Min; } };
//从下到上遍历 class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int row = triangle.size(); vector<vector<int> > path(row);//申请行空间,二维数组 int num = 0; for (int i=row-1; i>=0; i--) path[num++].resize(triangle[i].size(), 0);//申请列空间 int col = 0; int s = row; for (int i=0; i<row; i++){ s--; col = triangle[s].size(); for (int j=0; j<col; j++){ if (0 == i) path[i][j] = triangle[s][j]; else{ //当不是首尾数字的时候,看上一层相邻的两个数哪个更小更适合想加 path[i][j] = min(path[i-1][j], path[i-1][j+1]) + triangle[s][j]; } } } return path[row-1][0]; } };
原文:http://www.cnblogs.com/Kobe10/p/6360964.html