Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For 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).
Note:
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.

Problem Link: https://leetcode.com/problems/triangle/

PS:这里要注意一下"adjacent numbers on the row below"的具体含义，意思是（从上到下移步）下一个数字的行号是当前数字行号+1，且列号 >= 当前数字所在列号。例如：triangle[i][j] 只能向 triangle[i+1][j] 和 triangle[i+1][j+1] （在triangle[i+1][...]存在的情况下）移动。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();

        /* 1. 申请 （n+1）*（n+1） 维的int数组，
           因为是从底向上计算，最后一列res[n]的时候，将由res[n+1]列数组计算得到;
           由于该数组中每个元素初始化值都为0，所以不影响结果。
           2. res[i][j] 表示从triangle[i][j] 到 三角形底部的最小路径和。       
        */
        int[][] res = new int[n+1][n+1];

        for (int i = n-1; i >=0 ; i--) {
            for (int j = 0; j <= i; j++) {
                res[i][j] =Math.min(res[i+1][j], res[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        // 返回值表示从三角形最顶部到最底部的最小路径和。
        return res[0][0];
    }
}

该解决方案时间复杂度为o(n²)；
空间复杂度也为o(n²)，其中n为三角形的行数。

PS: 注意题目有明确说明，如果空间复杂度实现为o(n)将是一个加法点，那至少说明空间复杂度为o(n)的方法是存在的。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        /* 1. 申请 （n+1） 维的int数组，
           因为是从底向上计算，最后一列res[n]的时候，将由res[n+1]列数组计算得到.
           由于该数组中每个元素初始化都为0，所以不影响结果。
           2. res[j] 表示从triangle[i][j] 行到三角形底部的最小路径和,其中i将从n-1 到 0 进行循环。
           若暂时不能理解，请先看后续代码，在脑海中构想过程。
         */
        int[] res = new int[n+1];

        for (int i = n-1; i >=0 ; i--) {
            for (int j = 0; j <= i; j++) {
                res[j] =Math.min(res[j], res[j+1]) + triangle.get(i).get(j);// 想象从最后一列开始遍历，并记录该点到三角形底部的最小路径和。
            }
        }
        return res[0];
    }
}

该解决方案时间复杂度为o(n²)；
空间复杂度为o(n)，其中n为三角形的行数。