LeetCode 64.Minimum Path Sum (最小路径和)

女爷i 2022-05-10 05:40 170阅读 0赞

题目描述：

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

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

**示例:**

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

AC C++ Solution:

每个单元格的最小路径为 min(upsum,leftsum) + cur

所以方法和前两问大同小异。

class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            int m = grid.size();
            int n = grid[0].size();
            vector< vector<int>> sum(m,vector<int>(n,0));
            int count = 0;
            sum[0][0] = grid[0][0];
            
            for(int i = 1; i < n; i++)      //初始化首行
                sum[0][i] += sum[0][i-1] + grid[0][i];
            for(int j = 1; j < m; j++)      //初始化首列
                sum[j][0] += sum[j-1][0] + grid[j][0];
            
            for(int i = 1; i < m; i++)     
                for(int j = 1; j < n; j++) {
                    sum[i][j] = grid[i][j] + min(sum[i-1][j],sum[i][j-1]);
                }
            
            return sum[m-1][n-1];
            
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 64. Minimum Path Sum (动归)

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

曾经终败给现在/ 2024年04月17日 23:28/ 0 赞/ 47 阅读

相关 Minimum Path Sum（C++最小路径和）

（1）动态规划 class Solution { public: int minPathSum(vector<vector<int>>&

快来打我*/ 2022年10月11日 06:17/ 0 赞/ 156 阅读

相关 LeetCode64——Minimum Path Sum

LeetCode64——Minimum Path Sum 与[LeetCode63——Unique Path II][LeetCode63_Unique Path II] 类

红太狼/ 2022年08月09日 16:49/ 0 赞/ 142 阅读

相关 leetcode 64. Minimum Path Sum DP动态规划

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

逃离我推掉我的手/ 2022年06月09日 11:42/ 0 赞/ 155 阅读

相关 LeetCode 64.Minimum Path Sum (最小路径和)

题目描述：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例:

女爷i/ 2022年05月10日 05:40/ 0 赞/ 171 阅读

相关 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

╰半橙微兮°/ 2022年04月21日 22:08/ 0 赞/ 179 阅读

相关 LeetCode：64. Minimum Path Sum（最小路径问题）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

一时失言乱红尘/ 2022年04月05日 14:12/ 0 赞/ 322 阅读

相关【Leetcode】64. Minimum Path Sum（动态规划）

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

「爱情、让人受尽委屈。」/ 2022年02月27日 13:34/ 0 赞/ 169 阅读

相关 [Leetcode] Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

超、凢脫俗/ 2021年12月03日 07:19/ 0 赞/ 185 阅读

相关 LeetCod: 64. Minimum Path Sum 最小路径和

试题： Given a m x n grid filled with non-negative numbers, find a path from top left to

迷南。/ 2021年06月24日 16:10/ 0 赞/ 304 阅读