leetcode 64. Minimum Path Sum

妖狐艹你老母 2022-08-21 04:12 24阅读 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.

class Solution {
    public:
    	int minPathSum(vector<vector<int>>& grid) {
    		if (grid.empty())
    			return 0;
    		if (grid[0].empty())
    			return 0;
    		if (grid[0].size() == 1)
    		{
    			int re = 0;
    			for (int i = 0; i < grid.size(); i++)
    				re += grid[i][0];
    			return re;
    		}
    		if (grid.size() == 1)
    		{
    			int re = 0;
    			for (int i = 0; i < grid[0].size(); i++)
    				re += grid[0][i];
    			return re;
    		}
    		vector<int>gridminsum(grid[0].size());
    		gridminsum[0] = grid[0][0];
    		for (int i = 1; i < grid[0].size(); i++)
    			gridminsum[i] = grid[0][i]+gridminsum[i-1];
    		for (int i = 1; i < grid.size(); i++)
    		{
    			gridminsum[0] += grid[i][0];
    			for (int j = 1; j < grid[0].size(); j++)
    				gridminsum[j] = gridminsum[j - 1] + grid[i][j] < gridminsum[j]
    				+ grid[i][j] ? gridminsum[j - 1] + grid[i][j] : gridminsum[j] + grid[i][j];
    		}
    		vector<int>tt(grid[0].size());
    		tt[grid[0].size() - 1] = 0;
    		for (int i = grid[0].size() - 2; i >= 0; i--)
    			tt[i] = tt[i + 1] + grid[grid.size() - 1][i + 1];
    		int min = gridminsum[0] + tt[0];
    		for (int i = 1; i < grid[0].size(); i++)
    			if (gridminsum[i] + tt[i] < min)
    				min = gridminsum[i] + tt[i];
    		return min;
    	}
    };

accepted

发表评论取消回复

表情：

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

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

相关阅读

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

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

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

相关 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年08月21日 04:12/ 0 赞/ 25 阅读

相关 LeetCode64——Minimum Path Sum

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

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

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

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

相关 [Leetcode]-64 Minimum Path Sum

刚开始思考用递归来解决该问题： class Solution { public: int minSum(vector<vector<int>

忘是亡心i/ 2022年05月25日 03:29/ 0 赞/ 48 阅读

相关 LeetCode: Minimum Falling Path Sum

文章目录 Minimum Falling Path Sum 题目描述问题分析 C++实现 Scala实现

超、凢脫俗/ 2022年04月23日 09:10/ 0 赞/ 180 阅读

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

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

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