Related: Leetcode 120 - Triangle
http://www.programcreek.com/2013/01/leetcode-triangle-java/
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below
http://www.cnblogs.com/Xylophone/p/3888822.html
Lett and mps[i][j] denote the triangle and the minimum path sum from top to the j-th value in the i-th row, respectively. The following recursive equation can be observed:
t[i][j]=⎧⎩⎨mps[i−1][j]+t[i][j]mps[i−1][j−1]+t[i][j]min(t[i−1][j−1],t[i−1][j])+t[i][j]if j=0if j=iotherwise
http://yuanbin.gitbooks.io/algorithm/content/dynamic_programming/triangle.html
Method 1 - Traverse without hashmap: 2^n
递归遍历,逐个累加所有自上而下的路径长度,最后返回这些不同的路径长度的最小值。由于每个点往下都有2条路径,使用此方法的时间复杂度约为 O(2^n)
int minimumTotal(vector<vector<int> > &triangle) {
http://www.programcreek.com/2013/01/leetcode-triangle-java/
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
Bottom-Up: code from http://www.programcreek.com/2013/01/leetcode-triangle-java/11
(i.e., 2 + 3 + 5 + 1 = 11).http://www.cnblogs.com/Xylophone/p/3888822.html
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) { int[] total = new int[triangle.size()]; int l = triangle.size() - 1; for (int i = 0; i < triangle.get(l).size(); i++) { total[i] = triangle.get(l).get(i); } // iterate from last second row for (int i = triangle.size() - 2; i >= 0; i--) { for (int j = 0; j < triangle.get(i + 1).size() - 1; j++) { total[j] = triangle.get(i).get(j) + Math.min(total[j], total[j + 1]); } } return total[0]; }Top-Down code from http://www.darrensunny.me/leetcode-triangle/
Let
t[i][j]=⎧⎩⎨mps[i−1][j]+t[i][j]mps[i−1][j−1]+t[i][j]min(t[i−1][j−1],t[i−1][j])+t[i][j]if j=0if j=iotherwise
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if (triangle == null || triangle.size() == 0)
return 0;
// mps: minimum path sums from top to row i
int n = triangle.size();
int[] mps = new int[n];
mps[0] = triangle.get(0).get(0);
// Work on each row one at a time
for (int i = 1; i < n; i++) {
ArrayList<Integer> currenRow = triangle.get(i);
int temp1 = mps[0]; // Cache the value before it is overwritten
mps[0] += currenRow.get(0); // Only one path to the first value (all the way to the first)
for (int j = 1; j < i; j++) {
int temp2 = mps[j]; // Cache the value before it is overwritten
mps[j] = Math.min(temp1, temp2) + currenRow.get(j); // Select the smaller from the two possible ways
temp1 = temp2;
}
mps[i] = temp1 + currenRow.get(i); // Only one path to the last value (all the way to the last)
}
// Find the minimum path sum from top to bottom
int minimum = mps[0];
for (int i = 1; i < n; i++) {
minimum = Math.min(minimum, mps[i]);
}
return minimum;
}
Top-Down: do it in place: code from http://yucoding.blogspot.com/2013/04/leetcode-question-112-triangle.htmlint
minimumTotal(vector<vector<
int
> > &triangle) {
int
n = triangle.size();
if
(n==0){
return
0;}
for
(
int
i=1;i<n;i++){
for
(
int
j=0;j<triangle[i].size();j++){
if
(j==0){triangle[i][j] += triangle[i-1][j];}
if
(j>0){
if
(i>j){
triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]);
}
else
{
triangle[i][j] += triangle[i-1][j-1];
}
}
}
}
sort(triangle[n-1].begin(),triangle[n-1].end());
return
triangle[n-1][0];
}
http://yuanbin.gitbooks.io/algorithm/content/dynamic_programming/triangle.html
Method 1 - Traverse without hashmap: 2^n
递归遍历,逐个累加所有自上而下的路径长度,最后返回这些不同的路径长度的最小值。由于每个点往下都有2条路径,使用此方法的时间复杂度约为 O(2^n)
int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.empty()) {
return -1;
}
int result = INT_MAX;
dfs(0, 0, 0, triangle, result);
return result;
}
void dfs(int x, int y, int sum, vector<vector<int> > &triangle, int &result) {
const int n = triangle.size();
if (x == n) {
if (sum < result) {
result = sum;
}
return;
}
dfs(x + 1, y, (sum + triangle[x][y]), triangle, result);
dfs(x + 1, y + 1, (sum + triangle[x][y]), triangle, result);
}
int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.empty()) {
return -1;
}
int result = INT_MAX;
dfs(0, 0, 0, triangle, result);
return result;
}
void dfs(int x, int y, int sum, vector<vector<int> > &triangle, int &result) {
const int n = triangle.size();
if (x == n) {
if (sum < result) {
result = sum;
}
return;
}
dfs(x + 1, y, (sum + triangle[x][y]), triangle, result);
dfs(x + 1, y + 1, (sum + triangle[x][y]), triangle, result);
}
Method 3 - Divide and Conquer with Cache int minimumTotal(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;
}
int dfs(int x, int y, vector<vector<int> > &triangle, vector<vector<int> > &hashmap) {
const int n = triangle.size();
if (x == n) {
return 0;
}
// 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];
return hashmap[x][y];
}
Read full article from LeetCode - Triangle | Darren's Blog