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

迷南。 2021-06-24 16:10 281阅读 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.  
**代码：**  
由于只能往右或往下走，那么我们可以一行一行的统计出所有最小和。有四种情况：  
1、行列都为0  
2、行为0  
3、行不为0，列为0  
4、通用情况，从上，或者从左来的。

class Solution {
        public int minPathSum(int[][] grid) {
            if (grid==null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            int m = grid.length, n = grid[0].length;
            int[] dp = new int[n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i==0 && j==0) {
                        dp[j] = grid[i][j];
                    } else if (i == 0) {
                        dp[j] = dp[j - 1] + grid[i][j];
                    } else if(j==0){
                        dp[j] = dp[j] + grid[i][j];
                    }else{
                        dp[j] = Math.min(dp[j-1] + grid[i][j], dp[j] + grid[i][j]);
                    }
                }
            }
            return dp[n - 1];
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

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

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

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

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

相关 LeetCode64——Minimum Path Sum

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

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

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

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

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

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

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

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

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

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

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

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

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