my easy DP solution


  • 0
    E
    class Solution {
        public int minPathSum(int[][] grid) {
            
            if (grid == null || grid.length == 0) return 0;
            int width = grid[0].length;
            int[] dp = new int[width];
            for (int i = 0; i < width; i++) {
                dp[i] = Integer.MAX_VALUE;
            }
            dp[0] = 0;
            
            for (int row[] : grid) {
                
                for (int j = 0; j < width; j++) {
                    if (j == 0) dp[0] += row[0];
                    else
                        dp[j] = row[j] + Math.min(dp[j], dp[j-1]);
                }
            }
            return dp[width-1];
        }
    }

Log in to reply
 

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