Algorithm Puzzles: Minimum Path Sum

Posted on Edited on In Views: Word count in article: 160 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Algorithm Puzzles: Minimum Path Sum

Puzzle

Puzzle from leetcode:

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.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution final {
 public:
  int minPathSum(const std::vector<std::vector<int>>& grid) const {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    const int height = grid.size();
    const int width = grid[0].size();

    std::vector<std::vector<int>> dp(height,
                                     std::vector<int>(width, __INT_MAX__));

    dp[0][0] = grid[0][0];

    for (int y = 0; y < height; ++y) {
      int ly = std::max(y - 1, 0);
      for (int x = 0; x < width; ++x) {
        int lx = std::max(x - 1, 0);
        if (dp[y][x] == __INT_MAX__) {
          dp[y][x] = std::min(dp[ly][x], dp[y][lx]) + grid[y][x];
        }
      }
    }

    return dp[height - 1][width - 1];
  }
};