Karl's Nest
0%

leetcode-day-18

Posted on In
Day-18 Minimum Path Sum

LeetCode 30 days Challenge - Day 18

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

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.

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

Example:

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

Solution

题目要求分析：给定一个m x n的数组，每个元素代表该位置的路径代价，只能向下或向右移动，计算从左上角到右下角的最小代价路径。

解法：

非常简单的动态规划思想：

  1. 对每个位置，只能从上方或左边到来。
  2. 对第一行、第一列的位置，只能从左边、上方到来。
  3. 对其他位置，将路径代价从左到右、从上到下地更新为 该位置代价 + min(上方代价，左边代价) 即可。

最后，右下角元素的值即为最小代价路径。

1
2
3
4
5
6
7
8
9
10
int minPathSum(vector<vector<int>>& grid) {
    for (int i = 0; i<grid.size(); i++) {
        for (int j = 0; j<grid[0].size(); j++) {
            if (i == 0 && j > 0) grid[i][j] += grid[i][j-1];
            else if (i > 0 && j == 0) grid[i][j] += grid[i-1][j];
            else if (i > 0 && j > 0) grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid.back().back();
}

传送门：Minimum Path Sum

Karl