# Triangle - Find the minimum path sum from top to bottom

## Question

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

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.

Example
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).


## 题解

### C++ Traverse without hashmap

class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.empty()) {
return -1;
}

int result = INT_MAX;
dfs(0, 0, 0, triangle, result);

return result;
}

private:
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);
}
};


### 源码分析

dfs()的循环终止条件为x == n，而不是x == n - 1，主要是方便在递归时sum均可使用sum + triangle[x][y]，而不必根据不同的y和y+1改变，代码实现相对优雅一些。理解方式则变为从第x行走到第x+1行时的最短路径和，也就是说在此之前并不将第x行的元素值计算在内。

### C++ Divide and Conquer without hashmap

class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.empty()) {
return -1;
}

int result = dfs(0, 0, triangle);

return result;
}

private:
int dfs(int x, int y, vector<vector<int> > &triangle) {
const int n = triangle.size();
if (x == n) {
return 0;
}

return min(dfs(x + 1, y, triangle), dfs(x + 1, y + 1, triangle))  + triangle[x][y];
}
};


### C++ Divide and Conquer with hashmap

class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
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;
}

private:
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];
}
};


### Method 4 - Dynamic Programming

1. $(x,y)$ 出发走到最后一行的最短路径和
2. $(0,0)$ 走到 $(x,y)$的最短路径和

### C++ From Bottom to Top

class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.empty()) {
return -1;
}

vector<vector<int> > hashmap(triangle);

// get the total row number of triangle
const int 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];
}
}

return hashmap[0][0];
}
};


### 源码分析

1. 异常处理
2. 使用hashmap保存结果
3. 初始化hashmap[N-1][i], 由于是自底向上，故初始化时保存最后一行元素
4. 使用自底向上的方式处理循环
5. 最后返回结果hashmap[0][0]

### C++ From Top to Bottom

class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.empty()) {
return -1;
}

vector<vector<int> > hashmap(triangle);

// get the total row number of triangle
const int 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;
}
};


### Java From Top to Bottom

public class Solution {
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
public int minimumTotal(int[][] triangle) {
if (triangle == null || triangle.length == 0) return 0;
int[] last = new int[triangle.length];
int[] current = new int[triangle.length];
last[0] = triangle[0][0];
current[0] = last[0];
for (int i = 1; i < triangle.length; i++) {
for (int j = 0; j < i + 1; j++) {
int sum = Integer.MAX_VALUE;
if (j != 0) {
sum = triangle[i][j] + last[j - 1];
}
if (j != i) {
sum = Math.min(sum, triangle[i][j] + last[j]);
}
current[j] = sum;
}
for (int k = 0; k < i + 1; k++) last[k] = current[k];
}
int min = Integer.MAX_VALUE;
for (int n : current) {
min = Math.min(n, min);
}
return min;
}
}