## Minimum Path Sum

06/28/2016 Array Dynamic Programming

## Question

Given a $m * 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

Result: Accepted Time: 22 ms

Here should be some explanations.

int minPathSum(int** grid, int row, int col) {
for(int i = 1; i < row; i++)
grid[i][0]+=grid[i-1][0];
for(int i = 1; i < col; i++)
grid[0][i]+=grid[0][i-1];
for(int r = 1; r < row; r++)
for(int c = 1; c < col; c++)
grid[r][c] += grid[r-1][c] < grid[r][c-1] ? grid[r-1][c]:grid[r][c-1];
return grid[row-1][col-1];
}


Complexity Analytics

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n^2)$