# 120. Triangle

{% hint style="success" %}

### Key idea: memorize search＋from bottom to top

### 核心：记忆搜索＋自底而上

{% endhint %}

![List\<List\<Integer>> triangle actual shape](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-Lxxk6SR4QJ86SB7Keb4%2F-Lxxpuu498N3e6baMXMb%2F15.jpg?alt=media\&token=492ee04a-19ee-407d-9bd5-3510ecb8f261)

(0,0) -> (1,0), (1,1)

(1,0) -> (2,0), (2,1) ;    (1,1) -> (2,1), (2,2) ;

(2,0) -> (3,0), (3,1) ;     (2,1) -> (3,1), (3,2) ;     (2,2) -> (3,2), (3,3) ;

........

According to above, (2,1)   (3,1)   (3,2)  are repeated. If do regular DFS, every node has 2 choices, left or right in the next row. Therefore, time complexity is $$O(2^n)$$ . So another method is to store all the minimal path from any node to the last row. We let `dfs(int x, int y)` records the minimal path sum from `(x,y)` to the last row.

&#x20;`sumPath[x][y] = min(dfs(x+1, y),dfs(x+1, y+1)) + traingle[x][y]`

Space complexity is $$O(n^2)$$ (`sumPath[][]`). Because every node is only needed to compute once, there are $$(n(n+1))/2$$  times of computation, if every computation is $$O(1)$$ , then time complexity is $$O(n^2)$$&#x20;

If we do from bottom to up to record the minimal path for each node, we only need a `int[] minPath` to store the minimal path for each node of next row. Then taking advantage of `minPath[]` infers the minimal path of each node in current row. The result is `minPath[0][0]`. The space complexity is $$O(n)$$ , the time complexity is $$O(n^2)$$&#x20;

{% hint style="danger" %}
Deciding which part of the cache to discard to save space can be a hard job.

此题关键是，`dfs`记录当前状态到达目标状态的耗费，记忆化搜索就是`dfs`带值回来。

不仅要做DFS，还要自下而上方便存储，并且每次DFS要带值回来，`dfs(x,y)`即从`（x,y）`到终点的最短路径。

求最值一般可以用动态规划实现，而不是列举所有可能性。动态规划的精髓是记忆化搜索，记忆化搜索的精髓是自底而上，值可以被重复利用。
{% endhint %}

{% tabs %}
{% tab title="English" %}

#### DP is memorize search

Advantage: easy to think and implement

Disadvantage: Expensive memory cost
{% endtab %}

{% tab title="Chinese" %}

#### 动态规划的本质是记忆化搜索

优点：容易想到并实现

缺点：耗费存储空间
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Iterative" %}

```python
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        miniPath = [[0] * len(triangle[-1])] * len(triangle)
        for i in range(len(triangle[-1])):
            miniPath[-1][i] = triangle[-1][i]
            
        for i in reversed(range(len(triangle)-1)):
            for j in range(len(triangle[i])):
                miniPath[i][j] = min(miniPath[i+1][j], miniPath[i+1][j+1]) + triangle[i][j]
        
        print(miniPath)
        return miniPath[0][0]
```

{% endtab %}

{% tab title="Recursive" %}

```python
class Solution:    
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # edge case
        if len(triangle) == 0:
            return 0
        elif len(triangle) == 1:
            return triangle[0][0]

        l = len(triangle)
        sumPath = [[-1]*l for i in range(l)]
        return self.dfs(triangle, 0, 0, sumPath)
    
    def dfs(self, triangle, x, y, sumPath):
        # stop condition
        if x == len(triangle):
            return 0
        
        # regular case
        if sumPath[x][y] == -1:
            left = self.dfs(triangle,x+1,y, sumPath)
            right = self.dfs(triangle,x+1,y+1, sumPath)
            sumPath[x][y] = triangle[x][y] + min(left, right)

        return sumPath[x][y]
```

{% endtab %}
{% endtabs %}

### Python example 2: space complex = $$O(n)$$&#x20;

{% tabs %}
{% tab title="Java(T=O(n))" %}

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for(int i = triangle.size() - 2; i >= 0; i --)
            for(int j = triangle.get(i).size() - 1; j >= 0; j --) {
                int value = triangle.get(i).get(j) + Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1));
                triangle.get(i).set(j, value);
            }
        return triangle.get(0).get(0);
    }
}
```

{% endtab %}

{% tab title="Python(T=O(n), S=O(n))" %}

```python
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        miniPath = []
        for i in range(len(triangle[-1])):
            miniPath.append(triangle[-1][i])
            
        for i in reversed(range(len(triangle)-1)):
            for j in range(0, i+1):
                miniPath[j] = min(miniPath[j], miniPath[j+1]) + triangle[i][j]
                
        return miniPath[0]
```

{% endtab %}
{% endtabs %}

{% hint style="success" %}
自下而上用一个list记录每一行`(x,y)`的最小值，每一行迭代一次，都更新目前行的每个数据的最小值。
{% endhint %}