Minimum Path Sum

1package pkg5leetcode.top100;2 3/*4 * Minimum Path Sum | LC 645 * APPROACH: DP accumulate min path from top-left to each cell.6 * COMPLEXITY: Time O(m*n), Space O(1)7 */8public class top100_LC64MinimumPathSum {9    static int minPathSum(int[][] grid) {10        int m = grid.length, n = grid[0].length;11        for (int r = 0; r < m; r++) {12            for (int c = 0; c < n; c++) {13                if (r == 0 && c == 0) continue;14                if (r == 0) grid[r][c] += grid[r][c - 1];15                else if (c == 0) grid[r][c] += grid[r - 1][c];16                else grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]);17            }18        }19        return grid[m - 1][n - 1];20    }21 22    public static void main(String[] args) {23        check(minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}) == 7, "case1");24        check(minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}) == 12, "case2");25        System.out.println("all tests passed");26    }27 28    static void check(boolean cond, String name) {29        if (!cond) throw new AssertionError("FAILED: " + name);30        System.out.println("  PASS " + name);31    }32}