# 120. Triangle (1d)

![](/files/-MenmNzbpT_F6aUtliaE)

![](/files/-MenmSA5Fv2WMvlcWQb8)

## brute force, DFS, over time limit

recursion n levels,  **like leetcode 22**

choose element's left or right ...generate all possible solutions, 

time: O(n^2)

<https://leetcode-cn.com/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/>

## DFS + memoization

time: O(n^2)

space: O(n^2)

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        Integer[][] memo = new Integer[triangle.size()][triangle.size()]; // use Integer object!
        return divideAndConquer(triangle, 0, 0, memo);
        
    }
    private int divideAndConquer(List<List<Integer>> triangle, int x, int y, Integer[][] memo) {
        if (x == triangle.size()) { // reach last row
            return 0; // return no further ans
        }
        if (memo[x][y] != null) {
            return memo[x][y]; // if has cache, directly return it.
        }
        // do divide and conquer in two kinds of movement
        int move1 = divideAndConquer(triangle, x+1, y, memo); // next row, index y
        int move2 = divideAndConquer(triangle, x+1, y+1, memo); // next row, index y+1
        
        memo[x][y] = Math.min(move1, move2) + triangle.get(x).get(y); // do cache
        
        return memo[x][y];
    }
}

// row index: i
// next row, index i or i+1
/*
[2],
[3,4],
[6,5,7],
[4,1,8,3]
*/
```

## DP - bottom up

i: level 層數 j: element&#x20;

重複性: problem\[i, j] = min( sub(i+1, j), sub(i+1, j+1)) + a\[i, j]

state array: f\[i, j]

DP 方程：f\[i, j] = min( f(i+1, j), f(i+1, j+1)) + a\[i, j]

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

from bottom to calculate !

time: O(n^2)

space: O(n)

這裡其實改成只用1d 就達成, 因為不用開到 2d 就可以把結果算出來 (可以參考上面連結）

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // i: j
        // i+1: j, j+1 => select min value
        
        //          (2+9) = 11
        //     (3+6)    (4+6) 
        // (6+1)  (5+1)    (7+3)
        // 4      1       8     3 .from bottom 
        
        int dp[] = new int[triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}
```

#### follow up: use in-memory,&#x20;

#### 不開 dp\[], 直接把&#x20;

```java
 Math.min(dp[j], dp[j+1])
```

&#x20;加到&#x20;

```java
triangle 上面
```


---

# 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://timmybeeflin.gitbook.io/cracking-leetcode/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.