【称号】

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.

【Java代码】

public class Solution {

    /* 关键之处在于逆向思维。

     * 依据题意会自然而然地想从上而下逐层寻找最优解，可是因为下层元素比上层多。

     * 边界处的计算很繁琐。可是假设自下而上，逐层计算到当前层的最优解，那么

     * 到达最顶端时。就是所求最优解。

     */

    public int minimumTotal(List<List<Integer>> triangle) {

        //先处理特殊情况

        if (triangle == null || triangle.size() == 0) return 0;

        if (triangle.size() == 1) return triangle.get(0).get(0);

        int n = triangle.size();

        int[] below = new int[n];   //用于保存下一层的最优解

        int[] cur = new int[n];     //用于保存当前层的最优解

        int i, j;

        //初始值为最以下一行的值

        List<Integer> lastrow = triangle.get(n - 1);

        for (i = 0; i < n; i++) {

            below[i] = lastrow.get(i);

        }

        //从倒数第二行開始逐层向上计算

        for (i = n - 2; i >= 0; i--) {

            List<Integer> row = triangle.get(i);

            //从底层到当前层每一个位置的最优解取决于其下层临近的两个元素

            for (j = 0; j < row.size(); j++) {

                if (below[j] < below[j + 1]) cur[j] = below[j] + row.get(j);

                else cur[j] = below[j + 1] + row.get(j);

            }

            //层次向上移动，当前层变为下层

            for (j = 0; j < row.size(); j++) {

                below[j] = cur[j];

            }

        }

        return cur[0];

    }

}

【扩大】

除了最小输出值加法，如何找到这条道路？