/***
 * 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.
 */
public class Solution {
    // Solution 1: DP 
    // f[x][y] = min(f[x - 1][y], f[x][y - 1]) + gird[x][y], store path
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        int f[][] = new int[m][n];
        f[0][0] = grid[0][0];
        for (int i = 1; i < m; i++)
            f[i][0] = f[i - 1][0] + grid[i][0];
        for (int j = 1; j < n; j++)
            f[0][j] = f[0][j - 1] + grid[0][j];
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
        return f[m - 1][n - 1];
    }
}

@@ -274,16 +274,33 @@
 n 1: DP 
+O(m * n) O(m * n)
 %0A    // 
@@ -918,11 +918,486 @@
 %5D;%0A    %7D
+%0A%0A    // Solution 2: DP + Array O(m*n) O(n)%0A    public int minPathSum(int%5B%5D%5B%5D grid) %7B%0A        int m = grid.length;%0A        if (m == 0) return 0;%0A        int n = grid%5B0%5D.length;%0A        int f%5B%5D = new int%5Bn%5D;%0A        Arrays.fill(f, Integer.MAX_VALUE);%0A        f%5B0%5D = 0;%0A        for (int i = 0; i %3C m; i++) %7B%0A            f%5B0%5D += grid%5Bi%5D%5B0%5D;%0A            for (int j = 1; j %3C n; j++)%0A                f%5Bj%5D = min(f%5Bj - 1%5D, f%5Bj%5D) + grid%5Bi%5D%5Bj%5D;%0A        %7D%0A        return f%5Bn - 1%5D;%0A    %7D
 %0A%7D%0A

add MinimumPathSum.java