64. Minimum Path Sum

Minimum Path Sum

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.

Solution

public class Solution {
  public int minPathSum(int[][] grid) {
        int M = grid.length;
        int N = grid[0].length;

        int[][] X = new int[M][N];
        X[0][0] = grid[0][0];

        for(int i = 1; i < M; i ++) {
            X[i][0] = X[i-1][0] + grid[i][0];
        }

        for(int i = 1; i < N; i ++) {
            X[0][i] = X[0][i-1] + grid[0][i];
        }

        for(int i = 1; i < M; i ++) {
            for(int j = 1; j < N; j ++) {
                X[i][j] = Math.min(X[i-1][j], X[i][j-1]) + grid[i][j];
            }
        }

        return X[M-1][N-1];
    }
}