Simple java solution


  • 1
    H
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[] first = new int[col];
        int[] second = new int[col];
        int[] temp = new int[row];
        first[0] = grid[0][0];
        temp[0] = grid[0][0];
        for (int i = 1; i < col; i++) {
            first[i] = first[i-1] + grid[0][i];
        }
        for (int i = 1; i < row; i++) {
            temp[i] = temp[i-1] + grid[i][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (j == 0) {
                    second[j] = temp[i];
                } else {
                    second[j] = Math.min(first[j], second[j-1]) + grid[i][j];
                }
            }
            first = second;
        }
        return first[col - 1];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.