3ms clear java solution with DP


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

Log in to reply
 

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