Minimum Path Sum
Post
Cancel

# LeetCode #64: Minimum Path Sum (C/C++).

medium

source: https://leetcode.com/problems/minimum-path-sum/
C/C++ Solution to LeetCode problem 64. Minimum Path Sum.

## Problem

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.

## Examples

### Example 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.

### Example 2:

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

## Constraints

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

## Solution

We use dynamic programming:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { private: vector<vector<int>> dp; int minPath(vector<vector<int>>& grid, int r, int c) { if (r+1 == grid.size() && c+1 == grid.size()) return grid[r][c]; if (r == grid.size() || c == grid.size()) return INT_MAX; if (dp[r][c] != -1) return dp[r][c]; dp[r][c] = grid[r][c] + min(minPath(grid, r+1, c), minPath(grid, r, c+1)); return dp[r][c]; } public: int minPathSum(vector<vector<int>>& grid) { dp = vector(grid.size(), vector<int>(grid.size(), -1)); return minPath(grid, 0, 0); } };