剑指 Offer II 099. 最小路径之和

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         if (grid == null || grid.length == 0 && grid[0].length == 0) return 0;
  4.         int row = grid.length, col = grid[0].length;
  5.         // dp[i][j] 表示走到 [i][j] 总和最小的值
  6.         int[] dp = new int[col];
  8.         // base case
  9.         dp[0] = grid[0][0];
  10.         for (int i = 1; i < col; i++) {
  11.             dp[i] = dp[i - 1] + grid[0][i];
  12.         }
  13.         for (int i = 1; i < row; i++) {
  14.             for (int j = 0; j < col; j++) {
  15.                 if (j == 0) {
  16.                     dp[j] += grid[i][j];
  17.                 } else {
  18.                     dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
  19.                 }
  20.             }
  21.         }
  23.         return dp[col - 1];
  24.     }
  25. }