classSolution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ intminimumTotal(vector<vector<int> > &triangle){ if (triangle.empty()) { return-1; }
int result = INT_MAX; dfs(0, 0, 0, triangle, result);
return result; }
private: voiddfs(int x, int y, int sum, vector<vector<int> > &triangle, int &result){ constint n = triangle.size(); if (x == n) { if (sum < result) { result = sum; } return; }
classSolution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ intminimumTotal(vector<vector<int> > &triangle){ if (triangle.empty()) { return-1; }
int result = dfs(0, 0, triangle);
return result; }
private: intdfs(int x, int y, vector<vector<int> > &triangle){ constint n = triangle.size(); if (x == n) { return0; }
returnmin(dfs(x + 1, y, triangle), dfs(x + 1, y + 1, triangle)) + triangle[x][y]; } };
classSolution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ intminimumTotal(vector<vector<int> > &triangle){ if (triangle.empty()) { return-1; }
vector<vector<int> > hashmap(triangle); for (int i = 0; i != hashmap.size(); ++i) { for (int j = 0; j != hashmap[i].size(); ++j) { hashmap[i][j] = INT_MIN; } } int result = dfs(0, 0, triangle, hashmap);
return result; }
private: intdfs(int x, int y, vector<vector<int> > &triangle, vector<vector<int> > &hashmap){ constint n = triangle.size(); if (x == n) { return0; }
// INT_MIN means no value yet if (hashmap[x][y] != INT_MIN) { return hashmap[x][y]; } int x1y = dfs(x + 1, y, triangle, hashmap); int x1y1 = dfs(x + 1, y + 1, triangle, hashmap); hashmap[x][y] = min(x1y, x1y1) + triangle[x][y];
classSolution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ intminimumTotal(vector<vector<int> > &triangle){ if (triangle.empty()) { return-1; }
vector<vector<int> > hashmap(triangle);
// get the total row number of triangle constint N = triangle.size(); for (int i = 0; i != N; ++i) { hashmap[N-1][i] = triangle[N-1][i]; }
for (int i = N - 2; i >= 0; --i) { for (int j = 0; j < i + 1; ++j) { hashmap[i][j] = min(hashmap[i + 1][j], hashmap[i + 1][j + 1]) + triangle[i][j]; } }
classSolution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ intminimumTotal(vector<vector<int> > &triangle){ if (triangle.empty()) { return-1; }
vector<vector<int> > hashmap(triangle);
// get the total row number of triangle constint N = triangle.size(); //hashmap[0][0] = triangle[0][0]; for (int i = 1; i != N; ++i) { for (int j = 0; j <= i; ++j) { if (j == 0) { hashmap[i][j] = hashmap[i - 1][j]; } if (j == i) { hashmap[i][j] = hashmap[i - 1][j - 1]; } if ((j > 0) && (j < i)) { hashmap[i][j] = min(hashmap[i - 1][j], hashmap[i - 1][j - 1]); } hashmap[i][j] += triangle[i][j]; } }
int result = INT_MAX; for (int i = 0; i != N; ++i) { result = min(result, hashmap[N - 1][i]); } return result; } };