leetcode：64. 最小路径和

题目

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

示例 1：
[中等] 64. 最小路径和 - 图1

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

示例 2：

  1. 输入：grid = [[1,2,3],[4,5,6]]
  2. 输出：12

解答 & 代码

解法一：动态规划（二维）

  1. class Solution {
  2. public:
  3.     int minPathSum(vector<vector<int>>& grid) {
  4.         int rows = grid.size();
  5.         int cols = grid[0].size();
  6.         // 1. 动态规划数组：dp[i][j] 代表走到 grid[i][j] 的最小路径和
  7.         vector<vector<int>> dp(rows, vector<int>(cols, 0));
  9.         // 初始化
  10.         dp[0][0] = grid[0][0];
  11.         for(int j = 1; j < cols; ++j)                // 第零行
  12.             dp[0][j] = dp[0][j - 1] + grid[0][j];    
  13.         for(int i = 1; i < rows; ++i)                // 第零列
  14.             dp[i][0] = dp[i - 1][0] + grid[i][0];
  16.         // 状态转移
  17.         for(int i = 1; i < rows; ++i)
  18.         {
  19.             for(int j = 1; j < cols; ++j)
  20.                 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  21.         }
  23.         return dp[rows - 1][cols - 1];
  24.     }
  25. };

复杂度分析：m x n 网格 grid

  • 时间复杂度 O(m x n)：
  • 空间复杂度 O(m x n)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 77.22% 的用户
  4. 内存消耗：9.7 MB, 在所有 C++ 提交中击败了 59.14% 的用户

解法二：动态规划（空间压缩）

可以将二维 dp 数组压缩为一维行数组

  1. class Solution {
  2. public:
  3.     int minPathSum(vector<vector<int>>& grid) {
  4.         int rows = grid.size();
  5.         int cols = grid[0].size();
  6.         vector<int> dp(cols);
  8.         dp[0] = grid[0][0];
  9.         for(int j = 1; j < cols; ++j)
  10.             dp[j] = dp[j - 1] + grid[0][j];
  12.         for(int i = 1; i < rows; ++i)
  13.         {
  14.             dp[0] = dp[0] + grid[i][0];
  15.             for(int j = 1; j < cols; ++j)
  16.                 dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
  17.         }
  19.         return dp[cols - 1];
  20.     }
  21. };

复杂度分析：m x n 网格 grid

  • 时间复杂度 O(m x n)：
  • 空间复杂度 O(n)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 77.22% 的用户
  4. 内存消耗：9.4 MB, 在所有 C++ 提交中击败了 84.96% 的用户