Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

//f[i][j] = Math.min(f[i-1][j-1], f[i-1][j])+grid[i][j]

public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
    //O(n^2) space
    //f[i][j] = Math.min(f[i-1][j-1], f[i-1][j])+grid[i][j]
    if (triangle == null || triangle.size() == 0) {
        return 0;
    }
    int size = triangle.size();
    int[][] resultMap = new int[size][size];
    resultMap[0][0] = triangle.get(0).get(0);
    for (int i = 1; i < size; i++) {
        ArrayList<Integer> curr = triangle.get(i);
        for (int j = 0; j < curr.size(); j++) {
            if (j == 0) {
                resultMap[i][j] = resultMap[i - 1][j] + curr.get(j);
            } else {
                if (j < triangle.get(i - 1).size()) {
                    resultMap[i][j] = Math.min(resultMap[i - 1][j - 1], resultMap[i - 1][j]) + curr.get(j);
                } else {
                    resultMap[i][j] = resultMap[i - 1][j - 1] + curr.get(j);
                }
            }
        }
    }
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < size; i++) {
        if (resultMap[size - 1][i] < min) {
            min = resultMap[size - 1][i];
        }
    }
    return min;
}

Version 2. Bottom-Up O(n^2) space

可以想成求从底部任一点出发到左上角的最小路径和 代码简洁 不会outOfBound

    public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
    	if (triangle == null || triangle.size() == 0) {
    		return 0;
    	}
    	int size = triangle.size();
    	int[][] resultMap = new int[size][size];
    	//init the last row
    	ArrayList < Integer > lastRow = triangle.get(size - 1);
    	for (int i = 0; i < size; i++) {
    		resultMap[size - 1][i] = lastRow.get(i);
    	}
    	//from bottom to top
    	for (int i = size - 2; i >= 0; i--) {
    		ArrayList < Integer > curr = triangle.get(i);
    		for (int j = 0; j < curr.size(); j++) {
    			resultMap[i][j] = Math.min(resultMap[i + 1][j], resultMap[i + 1][j + 1]) + curr.get(j);
    		}
    	}
    	return resultMap[0][0];
    }

Version 3. Bottom-Up O(n) space

在Version 2的基础上 只用2*n的数组记录数据

代码不变 只需要行数mod 2 (modulus %) 就行了

    public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
    	if (triangle == null || triangle.size() == 0) {
    		return 0;
    	}
    	int size = triangle.size();
    	int[][] resultMap = new int[2][size];
    	//init the last row
    	ArrayList < Integer > lastRow = triangle.get(size - 1);
    	for (int i = 0; i < size; i++) {
    		resultMap[(size - 1) % 2][i] = lastRow.get(i);
    	}
    	//from bottom to top
    	for (int i = size - 2; i >= 0; i--) {
    		ArrayList < Integer > curr = triangle.get(i);
    		for (int j = 0; j < curr.size(); j++) {
    			resultMap[i % 2][j] = Math.min(resultMap[(i + 1) % 2][j], resultMap[(i + 1) % 2][j + 1]) + curr.get(j);
    		}
    	}
    	return resultMap[0][0];
    }

Share