【Leetcode】64. 最小路径和

题目

给定一个包含非负整数的 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,在选择的时候是从以前求出的若干个与本步骤相关的子问题中选最优的那个,加上这一步的值来构成这一步那个子问题的最优解。

状态转移方程:

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

1

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

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]]

相关阅读

原文发布于微信公众号 - Leetcode名企之路(DailyLeetCode)

原文发表时间:2018-09-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数值分析与有限元编程

有限元 | 二次样条梁单元

样条梁单元是样条函数与有限元法相结合的产物。有限元法将结构分割成若干单元,位移场采用分段插值或者分区插值。常用的插值方法有Lagrange插值,Hermite插...

3898
来自专栏小樱的经验随笔

Vijos P1497 立体图【模拟】

立体图 描述 小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。最近,他准备给小朋友讲解立体图,请你帮他画出立体图。 小渊有一块面积为m*n的...

3756
来自专栏人工智能LeadAI

pytorch入门教程 | 第二章:Autograd

autograd自动微分 假如我们有一个向量x=(1,1)当成input,经过一系列运算得到了output变量y,如下图所示: ? 如图所示,向量x经过与4和自...

39812
来自专栏崔庆才的专栏

Attention原理及TensorFlow AttentionWrapper源码解析

3.1K4
来自专栏CreateAMind

keras doc 9 预处理等

用以生成一个batch的图像数据,支持实时数据提升。训练时该函数会无限生成数据,直到达到规定的epoch次数为止。

2562
来自专栏闪电gogogo的专栏

压缩感知重构算法之正则化正交匹配追踪(ROMP)

  在看代码之前,先拜读了ROMP的经典文章:Needell D,VershyninR.Signal recovery from incompleteand i...

3666
来自专栏漫漫深度学习路

pytorch 学习笔记(一)

pytorch是一个动态的建图的工具。不像Tensorflow那样,先建图,然后通过feed和run重复执行建好的图。相对来说,pytorch具有更好的灵活性。...

5296
来自专栏漫漫深度学习路

pytorch学习笔记(二):gradient

gradient 在BP的时候,pytorch是将Variable的梯度放在Variable对象中的,我们随时都可以使用Variable.grad得到对应Var...

3158
来自专栏机器之心

教程 | 入门Python神经机器翻译,这是一篇非常精简的实战指南

传统意义上来说,机器翻译一般使用高度复杂的语言知识开发出的大型统计模型,但是近来很多研究使用深度模型直接对翻译过程建模,并在只提供原语数据与译文数据的情况下自动...

3091
来自专栏余林丰

12.高斯消去法(1)——矩阵编程基础

对于一阶线性方程的求解有多种方式,这里将介绍利用高斯消去法解一阶线性方程组。在介绍高斯消去法前需要对《线性代数》做一下温习,同时在代码中对于矩阵的存储做一个简...

2497

扫码关注云+社区

领取腾讯云代金券