小旭讲解 LeetCode 64. 最小路径和
文章目录

  • 原题
  • 思路
  • 参考

原题

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

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

示例:

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

思路

这道题目可以发现点(r, c)的最小路径由左侧点(r, c – 1) 和上面的点 (r – 1, c)来决定,即:

sum(r, c) = min(sum(r, c – 1), sum(r + 1, c)) + grid(r, c)]

故,每一个点我们都需要保留其最优值 —— 从起点到当前点的最小路径和,即所谓的最优子结构性质;同时,每一个点的最优值是由另外两个规模更小的点决定的,即所谓的重叠子问题性质

那么,我们可以使用动态规划的方式来解。

代码

class Solution { public:     int minPathSum(vector<vector<int>>& grid) {         int r = grid.size(), c = grid[0].size();         vector<vector<int>> dp(r, vector<int>(c, INT_MAX));         dp[0][0] = grid[0][0];         vector<int> d{0, -1, 0};         for (int cr = 0; cr < r; ++cr) {             for (int cc = 0; cc < c; ++cc) {                 for (int di = 0; di < 2; ++di) {                     int nr = cr + d[di];                     int nc = cc + d[di + 1];                     if (nr < 0 || nc < 0) continue;                     dp[cr][cc] = min(dp[cr][cc], dp[nr][nc] + grid[cr][cc]);                 }             }         }         return dp[r - 1][c - 1];     } };

复杂度分析

时间复杂度:O(R * C) R 代表行数,C代表列数
空间复杂度:O(R * C)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/minimum-path-sum/.

小旭讲解 LeetCode 64. 最小路径和leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 64. 最小路径和leetcode刷题题解