【Leetcode】64. 最小路径和

Leetcode名企之路

发布于 2018-10-09 12:00:30

8620

发布于 2018-10-09 12:00:30

文章被收录于专栏：Leetcode名企之路Leetcode名企之路

题目

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

题解

这种从左上角走到右下角的题目我们连续做了好几道的变种。为什么用DP?

DP vs 分治

dp和分治的不同之处在于分治分解而成的子问题必须没有联系（有联系的话就包含大量重复的子问题，那么这个问题就不适宜分治，虽然分治也能解决，但是时间复杂度太大，不划算），所以用dp的问题和用分治的问题的根本区别在于分解成的子问题之间有没有联系，这些子问题有没有重叠，即有没有重复子问题。

dp vs greedy

dp和贪心的不同之处在于每一次的贪心都是做出不可撤回的决策（即每次局部最优），而在dp中还有考察每个最优决策子序列中是否包含最优决策子序列，贪心中每一步都只顾眼前最优，并且当前的选择是不会依赖以前的选择的，而dp，在选择的时候是从以前求出的若干个与本步骤相关的子问题中选最优的那个，加上这一步的值来构成这一步那个子问题的最优解。

状态转移方程:

当在左上角的时候,dp[0][0] = grid[0][0];
当在第一行和第一列的时候,等于该位置的左边/上边 + 当前位置的数字;

其他位置,等于上一个状态中的最小值和当前的数字相加

2 如图所示,左边为矩阵,右边为dp状态记录. 求解问好所在位置的最小位置,看左边和上面的两个子问题最小的值。

java代码

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

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else if (i == 0) {
                    dp[i][j] = grid[i][j] + dp[i][j - 1];
                } else if (j == 0) {
                    dp[i][j] = grid[i][j] + dp[i - 1][j];
                } else {
                    dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];
    }
}

python代码

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[0][0] = grid[0][0]
                elif i == 0:
                    dp[i][j] = grid[i][j] + dp[i][j - 1]
                elif j == 0:
                    dp[i][j] = grid[i][j] + dp[i - 1][j]
                else:
                    dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
                print("i:" + str(i) + ",j:" + str(j) + ",grid:" + str(grid[i][j]) + ",dp:" + str(dp))
        return dp[-1][-1]

按照惯例,还是模拟一个简单例子看dp怎么更新:

    grid = [
        [1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]
    ]

i:0,j:0,grid:1,dp:[[1, 0, 0], [0, 0, 0], [0, 0, 0]]
i:0,j:1,grid:3,dp:[[1, 4, 0], [0, 0, 0], [0, 0, 0]]
i:0,j:2,grid:1,dp:[[1, 4, 5], [0, 0, 0], [0, 0, 0]]
i:1,j:0,grid:1,dp:[[1, 4, 5], [2, 0, 0], [0, 0, 0]]
i:1,j:1,grid:5,dp:[[1, 4, 5], [2, 7, 0], [0, 0, 0]]
i:1,j:2,grid:1,dp:[[1, 4, 5], [2, 7, 6], [0, 0, 0]]
i:2,j:0,grid:4,dp:[[1, 4, 5], [2, 7, 6], [6, 0, 0]]
i:2,j:1,grid:2,dp:[[1, 4, 5], [2, 7, 6], [6, 8, 0]]
i:2,j:2,grid:1,dp:[[1, 4, 5], [2, 7, 6], [6, 8, 7]]