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.
二维DP。设数组A[row][col],
Min[i][j] = min(Min[i-1][j],
Min[i][j-1]) +A[i][j];
注意初始条件即可。
public class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] sum = new int[m+2][n+2]; for(int i = 0; i < m + 2; i++){ for(int j = 0; j < n + 2; j++){ sum[i][j] = Integer.MAX_VALUE; } } sum[m][n+1] = 0; for(int i = m; i >= 1; i--){ for(int j = n; j >= 1; j--){ sum[i][j] = grid[i-1][j-1] + Math.min(sum[i+1][j], sum[i][j+1]); } } return sum[1][1]; } }
没必要用二维数组，用滚动数组即可。(TODO) 看水中的鱼