# 120. Triangle (1d)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MenSytVmlsxSgKFiPKU%2F-MenmNzbpT_F6aUtliaE%2Fimage.png?alt=media\&token=f666c26c-88b7-4402-ab45-012b03997137)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MenSytVmlsxSgKFiPKU%2F-MenmSA5Fv2WMvlcWQb8%2Fimage.png?alt=media\&token=c6816429-30c1-45ec-9770-b3786131b534)

## brute force, DFS, over time limit

recursion n levels,  **like leetcode 22**

choose element's left or right ...generate all possible solutions,&#x20;

time: O(n^2)

[https://leetcode-cn.com/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/](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 上面
```
