Minimum Path Sum
给一个2d数组, 里里面都是正整数, 问最小值的路径, 从左上到右下. 这个就是简单的dp, 因为我们只扫一次这个2d数组, 所以dp可以在数组里做.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class Solution { public int minPathSum(int[][] grid) { for(int i = 1; i < grid.length; i++) grid[i][0] += grid[i-1][0]; for(int i = 1; i < grid[0].length; i++) grid[0][i] += grid[0][i-1]; for(int i = 1; i < grid.length; i++) { for(int j = 1; j < grid[0].length; j++) grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1]) + grid[i][j]; } return grid[grid.length-1][grid[0].length-1]; } } |