Algorithm Puzzles everyday every week sometimes: Algorithm Puzzles: Minimum Path Sum
Puzzle
Puzzle from leetcode:
Given a m x n grid filled with nonnegative 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]; } };
