LeetCode - Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Solution1:

用2维DP数组，状态转移方程: f(i,j) = min(f(i-1, j),f(i, j-1)) + A[i][j]。

public int minPathSum0(int[][] grid) {
    int h = grid.length;
    int w = grid[0].length;
    int[][] f = new int[h][w];
    
    f[0][0] = grid[0][0];
    for(int i=1; i<h; i++) {
        f[i][0] = f[i-1][0]+grid[i][0];
    }
    for(int i=1; i<w; i++) {
        f[0][i] = f[0][i-1]+grid[0][i];
    }
    
    for(int i=1; i<h; i++) {
        for(int j=1; j<w; j++) {
            f[i][j] = Math.min(f[i-1][j], f[i][j-1]) + grid[i][j];
        }
    }
    
    return f[h-1][w-1];
}

 

Solution2:

用1维DP数组。f(j) = min( f(j), f(j-1) ) + A[i][j]。f(j)的值在遍历每一行时都会被更新一次。

	f(j)
f(j-1)	f(j)

 

public int minPathSum(int[][] grid) {
    int h = grid.length;
    int w = grid[0].length;
    int[] f = new int[w];
    for(int i=1; i<w; i++) { // f[0]初始值0, 其他为INT_MAX
        f[i] = Integer.MAX_VALUE;
    }
    
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            f[j] = Math.min(f[j], j>0?f[j-1]:Integer.MAX_VALUE) + grid[i][j];
        }
    }
    return f[w-1];
}

Reference:

http://www.cnblogs.com/TenosDoIt/p/3774804.html