# 120. Triangle

{% hint style="success" %}

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

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

{% endhint %}

![List\<List\<Integer>> triangle actual shape](/files/-Lxxpuu498N3e6baMXMb)

(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 %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/ix.-dynamic-programming/120.-triangle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.