LeetCode第64题 – 最小路径和

题目

解答

方案一：动态规划

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        for (int i = 1, imax = m; i < imax; ++i) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        for (int j = 1, jmax = n; j < jmax; ++j) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        for (int i = 1, imax = m; i < imax; ++i) {
            for (int j = 1, jmax = n; j < jmax; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
            }
        }

        return dp[m - 1][n - 1];
    }
}

方案二：递归

class Solution {
    public int minPathSum(int[][] grid, int m, int n) {
        if (m == 0 && n == 0) {
            return grid[0][0];
        }

        if (m == 0) {
            return minPathSum(grid, m, n - 1) + grid[m][n];
        }

        if (n == 0) {
            return minPathSum(grid, m - 1, n) + grid[m][n];
        }

        return Math.min(minPathSum(grid, m - 1, n) + grid[m][n], minPathSum(grid, m, n - 1) + grid[m][n]);
    }

    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        return minPathSum(grid, m - 1, n - 1);
    }
}

方案三：递归和备忘录

class Solution {
    public int minPathSum(int[][] grid, int[][] dp, int m, int n) {
        if (m == 0 && n == 0) {
            return grid[0][0];
        }

        if (m == 0) {
            return minPathSum(grid, dp, m, n - 1) + grid[m][n];
        }

        if (n == 0) {
            return minPathSum(grid, dp, m - 1, n) + grid[m][n];
        }

        if (dp[m - 1][n] == -1) {
            dp[m - 1][n] = minPathSum(grid, dp, m - 1, n);
        }

        if (dp[m][n - 1] == -1) {
            dp[m][n - 1] = minPathSum(grid, dp, m, n - 1);
        }

        return Math.min(dp[m - 1][n] + grid[m][n], dp[m][n - 1] + grid[m][n]);
    }

    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i][j] = -1;
            }
        }

        dp[0][0] = grid[0][0];
        return minPathSum(grid, dp, m - 1, n - 1);
    }
}

要点
本题目比较简单。

准备的用例，如下

@Before
public void before() {
    t = new Solution();
}

@Test
public void test001() {
    assertEquals(7, t.minPathSum(new int[][] { { 1, 3, 1 }, { 1, 5, 1 }, { 4, 2, 1 } }));
}

@Test
public void test002() {
    assertEquals(12, t.minPathSum(new int[][] { { 1, 2, 3 }, { 4, 5, 6 } }));
}