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.
Example 1:
1 2 3
|
[[1,3,1], [1,5,1], [4,2,1]]
|
Given the above grid map, return
. Because the path 1→3→1→1→1 minimizes the sum.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
|
class { public int minPathSum(int[][] grid) { if(grid == null || grid.length == 0) return 0; int m = grid.length; int n = grid[0].length; int sum = 0; int[][] dp = new int[m][n]; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(i==0 && j==0) dp[i][j] =grid[0][0]; else if(i == 0){ dp[i][j] = dp[i][j-1] + grid[i][j]; } else if(j==0){ dp[i][j] = dp[i-1][j] + grid[i][j]; } else{ dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } } return dp[m-1][n-1]; } }
|
- 这种情况下,不需要使用DP数组。使用DP数组的好处就是能够不改变Grid中的内容。
近期评论