64. Minimum Path Sum

╰半橙微兮° 2022-04-21 22:08 175阅读 0赞

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.

**Example:**

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

动态规划的典型用法。

class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
              if(grid.empty())
             return 0;
    
          int xLen = grid.size();
          int yLen = grid[0].size();
          vector<vector<int>> result(xLen);
          for(int i=0;i<xLen;i++)
              result[i].resize(yLen);
    
          result[0][0] = grid[0][0];
          for(int i=1;i<xLen;i++)
             result[i][0] = result[i-1][0] + grid[i][0];
    
          for(int j=1; j<yLen; j++)
             result[0][j] = result[0][j-1] + grid[0][j];
    
          for(int i=1;i<xLen;i++)
          {
            for(int j=1; j<yLen; j++)
            {
               result[i][j] = std::min(result[i][j-1], result[i-1][j]) + grid[i][j];
            }
          }
          return result[xLen-1][yLen-1]; 
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

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

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

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

相关 Minimum Path Sum

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

- 日理万妓/ 2022年09月26日 03:11/ 0 赞/ 108 阅读

相关 LeetCode64——Minimum Path Sum

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

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

相关 [leetcode] 64. Minimum Path Sum Add to List

64. Minimum Path Sum Add to List Given a m x n grid filled with non-negative numbers,

红太狼/ 2022年07月03日 18:59/ 0 赞/ 109 阅读

相关 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 赞/ 169 阅读

相关 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 赞/ 176 阅读

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

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

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

相关 #64 Minimum Path Sum——Top 100 Liked Questions

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

向右看齐/ 2022年01月29日 01:55/ 0 赞/ 130 阅读

相关 [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 赞/ 183 阅读