Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Solution:O(m*n)
public class Solution { public int minPathSum(int[][] grid) { int[] row = new int[grid[0].length]; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(j>0) row[j]=i>0?Math.min(row[j-1],row[j]):row[j-1]; row[j]+=grid[i][j]; } } return row[grid[0].length-1]; } }
Key Concept: Use DP and update previous and just use one dimension array
沒有留言:
張貼留言