Minimum Path Sum

06/28/2016 Array Dynamic Programming

Question

Given a 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:
  • Space Complexity: