Triangle 109

Question

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

Notice

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.

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

Solution

f[i][j]表示从(i,j)出发的path能取的最小值。

初始化：f[n-1][j]=triangle[n-1][j]，即最底部的点出发到达最低部的最小path为本身的值。

状态函数：f[i][j]=triangle[i][j]+min(f[i+1][j], f[i+1][j+1])，即从(i,j)出发的最小path为该点的值triangle[i][j]+下一行中和该点相邻的点的最小path。

优化：可以用滚动数组将f[n][n]优化为f[2][n]，因为f[i][j]只和下一行的值有关，因此可以只记录下一行的值和当前行的值，将真实的行数i%2之后即为在滚动数组中的行数。

代码如下：

public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        // write your code here
        if(triangle == null || triangle.length == 0){
            return 0;
        }

        if(triangle[0] == null || triangle[0].length == 0){
            return 0;
        }

        int n = triangle.length;
        int[][] f = new int[2][n];
        for(int i = 0; i < n; i++){
            f[(n - 1) % 2][i] = triangle[n - 1][i];
        }

        for(int i = n - 2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                f[i % 2][j] = triangle[i][j] + Math.min(f[(i + 1) % 2][j], f[(i + 1) % 2][j + 1]);
            }
        }

        return f[0][0];
    }
}