写这道题时候， 我还没学习过动态规划， 然后我从上往下写， 但明显代码没有从下往上优美。
JS版本（从上往下）：
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  for (let i = 1; i < triangle.length; i++) {
    for (let j = 0; j < triangle[i].length; j++) {
      const prev = triangle[i - 1];
      const cur = triangle[i];
      if (j === 0) triangle[i][j] += prev[0];
      else if (j === cur.length - 1) triangle[i][j] += prev[prev.length - 1];
      else triangle[i][j] += Math.min(prev[j - 1], prev[j]);
    }
  }
  return Math.min(...triangle[triangle.length - 1]);
};

JS版本（从下往上）：
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  const mini = triangle[triangle.length - 1];
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      mini[j] = triangle[i][j] + Math.min(mini[j], mini[j + 1]);
    }
  }
  
  return mini[0];
};

被mini数组的设定震惊到了。

PHP DP 自下而上的写法：


function minimumTotal($triangle)
    {
        for ($i = count($triangle) - 2; $i >= 0; $i--) {
            for ($j = 0; $j < count($triangle[$i]); $j++) {
                $triangle[$i][$j] = min($triangle[$i + 1][$j], $triangle[$i + 1][$j + 1]) + $triangle[$i][$j];
            }
        }
        return $triangle[0][0];
    }

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        
        //dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j];
        int row = triangle.size();
        //与C++代码的区别，初始数组没有赋值最后一层的元素
        int[] dp = new int[row+1];
        
        //从最后一层开始
        for(int i=row-1;i>=0;i--){
           //遍历列
           for(int j=0;j<triangle.get(i).size();j++){
              //递推公式
              dp[j] = triangle.get(i).get(j) + Math.min(dp[j],dp[j+1]);
           }
        }
        
        return dp[0];
    }
}

留言长度限制，只有分开了，这是动态规划的
动态规划：
```
    public static int minimumTotal(List<List<Integer>> triangle) {
        int level = triangle.size();
        List<Integer> min = new ArrayList<>(triangle.get(level - 1));
        for(int i = level - 2; i >= 0; i--) {
            int len = triangle.get(i).size();
            for(int j = 0, k = 0; j < len && k < len; j++, k++) {
                int tmp = Math.min(min.get(k), min.get(k + 1)) + triangle.get(i).get(j);
                min.set(j, tmp);
            }
            min.remove(min.size() - 1); // 每次重置后，最后一个就不需要了
        }
        return min.get(0);
    }
```

想法有了，但自己写折腾了好久，还是练的太少了，贴出来，有改进的地方希望提出来，大家共同学习~~

自顶向下：
```
    public int minimumTotal(List<List<Integer>> triangle) {
        int level = triangle.size();
        return helper(triangle, 0, 0, level);
    }
    
    // 参数i表示当前层，level表示共有多少层
    public int helper(List<List<Integer>> triangle, int i, int j, int level) {
        if(i >= level || j >= triangle.get(i).size())
            return 0;

        int left = helper(triangle, i + 1, j, level);
        int right = helper(triangle, i + 1, j + 1, level);

        return Math.min(left, right) + triangle.get(i).get(j);
    }
```

带备忘录的自顶向下：
```
    public static int minimumTotal(List<List<Integer>> triangle) {
        int level = triangle.size();
        List<List<Integer>> memory = new ArrayList<>();
        memory.add(new ArrayList<>());
        return helper(triangle, 0, 0, level, memory);
    }
    // 参数i表示当前层，level表示共有多少层
    public static int helper(List<List<Integer>> triangle, int i, int j, int level, List<List<Integer>> memory) {
        if(i >= level || j >= triangle.get(i).size())
            return 0;
        // 到了最后一层，就将结果全部放入
        if(i == level - 1 && memory.get(i).isEmpty()) {
            for(int k = 0; k < triangle.get(i).size(); k++)
                memory.get(i).add(triangle.get(i).get(k));
        }

        if(!memory.get(i).isEmpty() && j < memory.get(i).size() && memory.get(i).get(j) != null)
            return memory.get(i).get(j);

        if(memory.size() < level) // 防止添加回溯的过程又添加
            memory.add(new ArrayList<>());

        int left = helper(triangle, i + 1, j, level, memory);
        int right = helper(triangle, i + 1, j + 1, level, memory);
        memory.get(i).add(Math.min(left,right) + triangle.get(i).get(j));

        return memory.get(i).get(j);
    }
```

其实可以直接使用triangle本身的，不用额外申请数组
```
class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        for row in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[row])):
                triangle[row][j] = min(triangle[row + 1][j], triangle[row + 1][j + 1]) + triangle[row][j]

        return triangle[0][0]
```

老师讲的非常好，动态倒推的3部曲
1. 定义状态 dp[i][j] : 从底部到 triangel[i][j] 的路径的最小值
2.转移方程式: dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1]);
3.定义初始化的值: dp[rowMax][j] = triangle[rowMax][j]

我总感觉用二维数组存储更好理解，老师的代码里面是用 一维数组存储 最小值，感觉很N,但对于初学者 有点 看不太懂

for (int i = rowMax-1; i >=0 ; i--) {
    for (int j = 0; j <=colMax && triange[i][j] >0 (假设 0是初始值) ;j ++ ) {
        dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1]);
    }
}
return dp[0][0];