3 ms DP with extra O(n) space in Java


  • 0
    Y

    public class Solution {

         int []a;
         a = new int[grid[0].length];
         if(grid[0].length==1){
             if(grid.length==0) return grid[0][0];
             for(int i=1; i<grid.length; i++){
                 a[i] += a[i-1];
             }
             return grid[0][grid.length-1];
         }
         
         a[0] = grid[0][0];
         for(int i=1; i<grid[0].length; i++){
             a[i] = grid[0][i] + a[i-1];
         }
         
         for(int j=1; j<grid.length; j++){
             a[0] = a[0] + grid[j][0];
             for(int i=1; i<grid[0].length; i++){
                 a[i] = Math.min(a[i-1] + grid[j][i], a[i] + grid[j][i]);
             }
         }
         return a[grid[0].length-1];
     }
    }

Log in to reply
 

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