### 120. Triangle

Given a triangle array, return the `minimum path sum` from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either `index i` or `index i + 1` on the next row.

Example 1:

``````Input: triangle = [[2], [3,4], [6,5,7], [4,1,8,3]]
2 3 6 1
2 3 5 1
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).``````

Example 2:

``````Input: triangle = [[-10]]
Output: -10``````
• Constraints:
• 1 <= triangle.length <= 200
• triangle0.length == 1
• trianglei.length == trianglei - 1.length + 1
• -104 <= trianglei <= 104

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

### Analyze

``````2
3 4
6 5 7
4 1 6 8``````

``````/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
const cache = { smallest: Infinity }
getSmaller(triangle, 0, 0, 0, cache)
return cache.smallest
}

// m: witch row
// n: witch column
// result: current min value
var getSmaller = function(triangle, m, n, result, cache) {
const sum = result + (triangle[m][n] ? triangle[m][n] : 0)
if (m === triangle.length - 1) {
cache.smallest = Math.min(cache.smallest, sum)
return
}

getSmaller(triangle, m + 1, n, sum, cache)
getSmaller(triangle, m + 1, n + 1, sum, cache)
}``````

``````/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
return getSmaller(triangle, 0, 0)
}

// m: witch row
// n: witch column
var getSmaller = function(triangle, m, n) {
console.log('m', m, 'n', n, 'triangle', triangle[m][n])
if (m === triangle.length - 1) {
return triangle[m][n]
}
const a = getSmaller(triangle, m + 1, n)
const b = getSmaller(triangle, m + 1, n + 1)
return (a < b ? a : b) + triangle[m][n]
}``````

`var triangle = [[2], [3,4], [6,5,7], [4,1,8,3]]` 为例, 当前 `getSmaller` 函数执行次数为 15。调用栈如下:

``````2
3 4
6 5 7
4 1 8 3

m 0 n 0 triangle 2
m 1 n 0 triangle 3
m 2 n 0 triangle 6
m 3 n 0 triangle 4
m 3 n 1 triangle 1
m 2 n 1 triangle 5 <-
m 3 n 1 triangle 1 <-
m 3 n 2 triangle 8 <-
m 1 n 1 triangle 4
m 2 n 1 triangle 5 <-
m 3 n 1 triangle 1 <-
m 3 n 2 triangle 8 <-
m 2 n 2 triangle 7
m 3 n 2 triangle 8
m 3 n 3 triangle 3``````

``````/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
return getSmaller(triangle, 0, 0, {})
}

// m: witch row
// n: witch column
var getSmaller = function(triangle, m, n, cache) {
console.log('m', m, 'n', n, 'triangle', triangle[m][n])
if (m === triangle.length - 1) {
return triangle[m][n]
}
const a = typeof cache[`\${m + 1}_\${n}`] === 'number'
? cache[`\${m + 1}_\${n}`]
: getSmaller(triangle, m + 1, n, cache)
const b = typeof cache[`\${m + 1}_\${n + 1}`] === 'number'
? cache[`\${m + 1}_\${n + 1}`]
: getSmaller(triangle, m + 1, n + 1, cache)
const result = (a < b ? a : b) + triangle[m][n]
cache[`\${m}_\${n}`] = result
return result
}``````

``````m 0 n 0 triangle 2
m 1 n 0 triangle 3
m 2 n 0 triangle 6
m 3 n 0 triangle 4
m 3 n 1 triangle 1
m 2 n 1 triangle 5 <-
m 3 n 1 triangle 1 <-
m 3 n 2 triangle 8 <-
m 1 n 1 triangle 4
m 2 n 2 triangle 7
m 3 n 2 triangle 8
m 3 n 3 triangle 3``````

``````/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
let result = Infinity
for (let n = 0; n < triangle[triangle.length - 1].length; n++) {
const value = getSmaller(triangle, triangle.length - 1, n)
result = Math.min(value, result)
}
return result
}

var getSmaller = function(triangle, m, n) {
if (m === 0) {
return triangle[m][n]
}

const a = getSmaller(triangle, m - 1, n)
if (triangle[m - 1][n - 1] === undefined) {
return a + triangle[m][n]
}

const b = getSmaller(triangle, m - 1, n - 1)
return (a < b ? a : b) + triangle[m][n]
}``````

``````/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
const arr = []
for (let m = triangle.length - 1; m >= 0; m--) {
for (let n = 0; n <= m; n++) {
if (!arr[m]) arr[m] = []
if (!arr[m + 1]) {
arr[m][n] = triangle[m][n]
} else {
arr[m][n] = Math.min(arr[m + 1][n], arr[m + 1][n + 1]) + triangle[m][n]
}
}
}
return arr[0][0]
}``````

64