120 Triangle 参考程序 Java/C++/Python

/** * 本代码由九章算法编辑提供。没有版权欢迎转发。 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。 * - 现有的面试培训课程包括：九章算法班，系统设计班，九章强化班，Java入门与基础算法班， * - 更多详情请见官方网站：http://www.jiuzhang.com/ */// version 0: top-downpublic class Solution {    /**     * @param triangle: a list of lists of integers.     * @return: An integer, minimum path sum.     */    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[x][y] = minimum path value from 0,0 to x,y        int n = triangle.length;        int[][] f = new int[n][n];                // initialize         f[0][0] = triangle[0][0];        for (int i = 1; i < n; i++) {            f[i][0] = f[i - 1][0] + triangle[i][0];            f[i][i] = f[i - 1][i - 1] + triangle[i][i];        }                // top down        for (int i = 1; i < n; i++) {            for (int j = 1; j < i; j++) {                f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];            }        }                // answer        int best = f[n - 1][0];        for (int i = 1; i < n; i++) {            best = Math.min(best, f[n - 1][i]);        }        return best;    }}//Version 1: Bottom-Uppublic class Solution {    /**     * @param triangle: a list of lists of integers.     * @return: An integer, minimum path sum.     */    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[x][y] = minimum path value from x,y to bottom        int n = triangle.length;        int[][] f = new int[n][n];                // initialize         for (int i = 0; i < n; i++) {            f[n - 1][i] = triangle[n - 1][i];        }                // bottom up        for (int i = n - 2; i >= 0; i--) {            for (int j = 0; j <= i; j++) {                f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j];            }        }                // answer        return f[0][0];    }}//Version 2 : Memorize Searchpublic class Solution {    private int n;    private int[][] minSum;    private int[][] triangle;    private int search(int x, int y) {        if (x >= n) {            return 0;        }        if (minSum[x][y] != Integer.MAX_VALUE) {            return minSum[x][y];        }        minSum[x][y] = Math.min(search(x + 1, y), search(x + 1, y + 1))            + triangle[x][y];        return minSum[x][y];    }    public int minimumTotal(int[][] triangle) {        if (triangle == null || triangle.length == 0) {            return -1;        }        if (triangle[0] == null || triangle[0].length == 0) {            return -1;        }                this.n = triangle.length;        this.triangle = triangle;        this.minSum = new int[n][n];        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                minSum[i][j] = Integer.MAX_VALUE;            }        }        return search(0, 0);    }}