首页 > 其他分享 >64 - Minimum Path Sum 最小路径和

64 - Minimum Path Sum 最小路径和

时间:2024-05-14 22:51:49浏览次数:30  
标签:int Sum 路径 最小 Minimum grid Path 64 dp

64 - Minimum Path Sum 最小路径和

问题描述

 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.

解释:
给定m*n 的矩阵,里面都是非负整数,找到一条从左上角到右下角的路径,使得其和最小。每一次移动只能向右或者向下移动

案例:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

给定如上数组,可以明确知道从左上到右下的最小路径和为图中黄色图形

基本思想

二维动态规划问题,假设grid数组 m行,n列。构建同等大小的数组dp

则 \(dp[i][j]\) : 表示 由 [0,0] 位置 到 [i,j] 位置的最小路径和,由于只能向下或者向右移动,故 \(dp[i][j]\) 更新公式如下:

\(dp[i][j]\) = min( \(dp[i-1][j]\), \(dp[i][j-1]\)) + \(grid[i][j]\)

时间复杂度,空间复杂度都为\(o(n^2)\)

代码

C++

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        if(m<=0) return 0;
        int n = grid[0].size();
        if(n<=0) return 0;
        vector<vector<int>> dp(m, vector<int>(n,0));
        //1-初始化
        dp[0][0] = grid[0][0];
        for(int i=1;i<m;++i) {
            dp[i][0] = grid[i][0] + dp[i-1][0];
        }
        for(int i=1;i<n;++i) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for(int i=1;i<m;++i) {
            for(int j=1;j<n;++j) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }

python

    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if m <= 0: return 0
        n = len(grid[0])
        if n <= 0: return 0
        dp = [[0 for j in range(n)] for i in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        return dp[m-1][n-1]

标签:int,Sum,路径,最小,Minimum,grid,Path,64,dp
From: https://www.cnblogs.com/douniwanli/p/18192454

相关文章

  • h5 页面播放base64编码的audio数据
    例子:<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>audiotest</title&......
  • AtCoder Beginner Contest 351 E - Jump Distance Sum
    题目链接Hint1:只能斜着走,容易想到黑白棋盘,\((x+y)\%2==0\)位于一个团,\((x+y)\%2==1\)位于另一个团,分别求和。Hint2:\(dist=max(|x1-x2|,|y1-y2|)\),这是切比雪夫距离,将坐标系倾斜\(45^{\circ}\),改为曼哈顿距离\(dist=|x1-x2|+|y1-y2|\),即\(X=x+y,Y=x-y\),这样就可以将横纵坐标......
  • x64汇编——汇编指令
     汇编指令 movdest,srcmovmove的简称将src的内容赋值给dest,类似于dest=src[地址值]中扩号[]里面放的都是内存地址一个变量的地址值,是它所有字节地址中的最小值word是2字节,dword是4字节(doubleword),qword是8字节(quadword)  注意地址取值是向高位扩展,如......
  • C#实现图片转Base64字符串.并支持markdown文件打开展示
    引用1.0.3版本或以上的Wesky.Net.OpenTools包1.0.3版本提供图片转Base64字符串方案,并提供根据后缀名自动识别Mime类型,合成标准URI开源项目地址:Gitee:https://gitee.com/dreamer_j/open-tools.gitGithub:https://github.com/LittleLittleRobot/OpenTools.git为了简单操作......
  • 加密测试-base64加密
    1.由于jmeter自带函数没有base64加密解密,需要额外安装自定义函数,大体步骤:jmeter安装插件管理>通过插件管理安装自定义函数,步骤详看:https://www.cnblogs.com/sheepboy/p/18177703方式1:使用base64Encode函数加密      ${__base64Encode(待加密的字符串,)} 方式2:使用前......
  • Rocketmq 不同的topic要配不同的consumegroup
    Rocketmq不同的topic要配不同的consumegroup使用Rocketmq一定要注意,如果项目中要订阅两个topic,一定要保证consumeGroup是两个不同的。这是因为,Consumer会定期发送心跳,默认是30s一次。心跳会像全部broker发送,心跳包内容包括groupname,topicname1。然后broker端会......
  • Topcoder SRM647-Div1-Lv2 CtuRobots
    涉及知识点:动态规划题意有\(n\(\leq500)\)个机器人,每个机器人的价格为\(cost_i\(\leq10^4)\),油箱容量为\(cap_i\(\leq10^9)\),一单位燃料可以走一单位距离,你可以给购买的机器人编号,机器人\(k\)可以给机器人\(k+1\)补充燃料,但是任意时刻机器人的燃料不能超过其油箱......
  • Red Hat Enterprise Linux (RHEL) 9.4 发布 (x86_64, aarch64) - 红帽企业 Linux
    RedHatEnterpriseLinux(RHEL)9.4发布(x86_64,aarch64)-红帽企业Linux红帽企业Linux9请访问原文链接:RedHatEnterpriseLinux(RHEL)9.4(x86_64,aarch64)-红帽企业Linux,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org红帽企业Linux9红帽企......
  • LeetCode 1186. Maximum Subarray Sum with One Deletion
    原题链接在这里:https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/description/题目:Givenanarrayofintegers,returnthemaximumsumfora non-empty subarray(contiguouselements)withatmostoneelementdeletion. Inotherwords,youwa......
  • P5664 [CSP-S2019] Emiya 家今天的饭
    题意简述有\(n\)种方法和\(m\)种食材,第\(i\)种方法第\(j\)种食材做出来的菜有\(a_{i,j}\)种。有以下限制:至少做一盘菜。每种方法做出来的菜品数至多为\(1\)。所有以第\(i\)种食材做出来的菜品数不超过菜品种数的一半。求方案数。\(n\le100,m\le2\times10^......