> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/109triangle.md).

# 109.Triangle

## 1.Description(Easy)

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

### Notice

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

**Example**

Given the following triangle:

```
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
```

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

## 2.Code

经典dynamic programming题目

解决方法：

• DFS: Traverse

• DFS: Divide Conquer

• Divide Conquer + Memorization

• Traditional Dynamic Programming

1.Traverse:要用全局变量来记录最优值，超时

2.Divided Conquer--超时

3.记忆化搜索（recursive）:Divided Conquer+ Memorization

中间很多点重复计算，去除这些，让程序记录下来结果不要做重复的事，用hash/int\[]\[]

![](https://3755400284-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M33ghpQv0ZbnP8UX-Qg%2F-M33gjHLI-_g2orPt5LN%2F-M33h-bA0PGLbRsYy5ZN%2Fimport6.png?generation=1584921844909409\&alt=media)

4.DP:时间O(n\*n) ，空间 O(n\*n)

**Bottom up 自底向上（从(x,y)走到bottom）,最后返回最上层f\[0]\[0].**

![](https://3755400284-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M33ghpQv0ZbnP8UX-Qg%2F-M33gjHLI-_g2orPt5LN%2F-M33h-bCVu668wR3q1Ar%2Fimport7.png?generation=1584921844532510\&alt=media)

**Top Down 自顶向下 （从(0,0)走到(x,y) ）**![](https://3755400284-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M33ghpQv0ZbnP8UX-Qg%2F-M33gjHLI-_g2orPt5LN%2F-M33h-bEDqrzugrhLsSv%2Fimport5.png?generation=1584921844556108\&alt=media)

```
 public int minimumTotal(int[][] triangle) {
    if (triangle == null || triangle.length == 0) {
           return -1;
       }
       if (triangle[0] == null || triangle[0].length == 0) {
           return -1;
       }

       //state:f is the min sum  from(x,y) to the bottom
       int n=triangle.length;
       int[][] f=new int[n][n];

       //Initialization:
       for(int i=0;i<n;i++){
           f[n-1][i]=triangle[n-1][i];
       }

       //function:
       for(int i=n-2;i>=0;i--){
           for(int j=i;j>=0;j--){
               f[i][j]=Math.min(f[i+1][j],f[i+1][j+1])+triangle[i][j];
           }           
      }

       return f[0][0];


    }
```