DP Time: 0(mn) Space: O(n)


  • 0
    public class Solution {
        public int minPathSum(int[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            int[] table = new int[n];
            table[0] = grid[0][0];
            for (int i = 1; i < n; i++) {
                table[i] = table[i - 1] + grid[0][i];
            }
            for (int i = 1; i < m; i++) {
                table[0] += grid[i][0];
                for (int j = 1; j < n; j++) {
                    table[j] = Math.min(table[j], table[j - 1]) + grid[i][j];
                }
            }
            return table[n - 1];
        }
    }
    

Log in to reply
 

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