Minimum Path Sum

Medium

Python

def min_path_sum(grid):
    m,n=len(grid),len(grid[0])
    for i in range(m):
        for j in range(n):
            if i==0 and j==0: continue
            elif i==0: grid[i][j]+=grid[i][j-1]
            elif j==0: grid[i][j]+=grid[i-1][j]
            else: grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
    return grid[m-1][n-1]

Java

public int minPathSum(int[][] grid){
    int m=grid.length,n=grid[0].length;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++){
            if(i==0&&j==0) continue;
            else if(i==0) grid[i][j]+=grid[i][j-1];
            else if(j==0) grid[i][j]+=grid[i-1][j];
            else grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
        }
    return grid[m-1][n-1];
}

Key Insight

In-place DP. min() vs Math.min(). elif vs else if.

Python → Java Differences

min() vs Math.min()
In-place DP identical
elif vs else if

Python

def min_path_sum(grid):
    m,n=len(grid),len(grid[0])
    for i in range(m):
        for j in range(n):
            if i==0 and j==0: continue
            elif i==0: grid[i][j]+=grid[i][j-1]
            elif j==0: grid[i][j]+=grid[i-1][j]
            else: grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
    return grid[m-1][n-1]

Java

public int minPathSum(int[][] grid){
    int m=grid.length,n=grid[0].length;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++){
            if(i==0&&j==0) continue;
            else if(i==0) grid[i][j]+=grid[i][j-1];
            else if(j==0) grid[i][j]+=grid[i-1][j];
            else grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
        }
    return grid[m-1][n-1];
}

Algorithm Steps

1. First row/col one direction
2. Others: min of top and left
3. Return bottom-right

← Previous All Dynamic Programming