# 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) {
// write your code here
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;
}
}