解法一：动态规划

基本同剑指 Offer 47. 礼物的最大价值

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int row = grid.length;
  4.         int col = grid[0].length;
  5.         // dp[i][j]表示到达(i, j)时的路径最小和
  6.         int[][] dp = new int[row][col];
  7.         dp[0][0] = grid[0][0];
  8.         for (int i = 1; i < row; ++i) {
  9.             dp[i][0] = dp[i - 1][0] + grid[i][0];
  10.         }
  11.         for (int i = 1; i < col; ++i) {
  12.             dp[0][i] = dp[0][i - 1] + grid[0][i];
  13.         }
  14.         for (int i = 1; i < row; ++i) {
  15.             for (int j = 1; j < col; ++j) {
  16.                 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  17.             }
  18.         }
  19.         return dp[row - 1][col - 1];
  20.     }
  21. }