返回

[Leetcode]64. Minimum Path Sum(C++)

题目描述

题目链接:64. Minimum Path Sum

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.

例子

例子 1

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

例子 2

Input: grid = [[1,2,3],[4,5,6]] Output: 12

Note

You can only move either down or right at any point in time.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

解题思路

这道题可以用动态规划来思路来做,最简单的思路是创建一个相等大小的二维数组 minSum[m][n], 其中 minSum[i][j] 表示从左上角到对应位置的最小路径和,由题目得知路径只能往下或往右走,因此状态转移方程为: minSum[i][j] = grid[i][j] + min(minSum[i][j-1], minSum[i-1][j])(注意边界条件)。但注意到我们从头到尾只会同时使用两行数据,因此我们可以将其简化为使用一维数组进行更新可以,具体参考以下代码:

#include <vector>

class Solution {
public:
    int minPathSum(std::vector<std::vector<int>>& grid) {
        std::vector<int> current_row = grid[0];
        for (int i = 0; i < grid.size(); ++i) {
            // iteratively update min sum for each row, we only need the result of the last row
            calMinSum(grid, current_row, i);
        }
        return current_row.back();
    }

private:
    void calMinSum(const std::vector<std::vector<int>>& grid, std::vector<int>& current_row, int next_row_idx) {

        for (int i = 0; i < current_row.size(); ++i) {
            
            if (next_row_idx == 0) {
                // #1: if the first row, simply add min sum from left side
                current_row[i] += (i == 0? 0 : current_row[i - 1]); 
            }
            else if (i == 0) {
                // #2: if the first element, simply add min sum from upper grid
                current_row[i] += grid[next_row_idx][i];
            }
            else {
                // #3: general case: choose min sum between left and upper side
                current_row[i] = std::min(current_row[i], current_row[i - 1]) + grid[next_row_idx][i];
            }
        }
    }
};
  • 时间复杂度: O(mn)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 64.MinimumPathSum.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy