/**

 * Source : https://oj.leetcode.com/problems/triangle/

 *

 *

 * 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.

 *

 */

public class Triangle {

    /**

     * 求出三角形中和最小的路径

     * 使用常数空间O(n)

     * 从最后一层开始计算，第i层的个数为i个，每个元素和第i+1层的左右下角两个元素中较小的一个进行求和作为该位置新的元素

     *

     *

     * @param triangle

     * @return

     */

    public int getMinimumPath (int[][] triangle) {

        if (triangle.length == 0) {

            return 0;

        }

        int m = triangle.length;

        int n = triangle[0].length;

        int[] result = triangle[triangle.length-1];

        for (int i = m-2; i >= 0; i--) {

            for (int j = 0; j <= i; j++) {

                result[j] = Math.min(result[j], result[j+1]) + triangle[i][j];

            }

        }

        return result[0];

    }

    public static void main(String[] args) {

        Triangle triangle = new Triangle();

        int[][] arr = new int[][]{

                {2},

                {3,4},

                {6,5,7},

                {4,1,8,3}

        };

        System.out.println(triangle.getMinimumPath(arr));

    }

}