Minimum Path Sum

描述

Given a m × 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

分析

跟第 ??? 节 Unique Paths 很类似。

设状态为f[i][j]，表示从起点(0,0)到达(i,j)的最小路径和，则状态转移方程为：

  1. f[i][j]=min(f[i-1][j], f[i][j-1])+grid[i][j]

备忘录法

  1. // Minimum Path Sum
  2. // 备忘录法
  3. public class Solution {
  4.     public int minPathSum(int[][] grid) {
  5.         final int m = grid.length;
  6.         final int n = grid[0].length;
  7.         this.f = new int[m][n];
  8.         for (int i = 0; i < m; ++i) Arrays.fill(f[i], -1);
  9.         return dfs(grid, m-1, n-1);
  10.     }
  12.     private int dfs(int[][] grid, int x, int y) {
  13.         if (x < 0 || y < 0) return Integer.MAX_VALUE; // 越界，终止条件，注意，不是0
  15.         if (x == 0 && y == 0) return grid[0][0]; // 回到起点，收敛条件
  17.         return Math.min(getOrUpdate(grid, x - 1, y),
  18.                 getOrUpdate(grid, x, y - 1)) + grid[x][y];
  19.     }
  21.     private int getOrUpdate(int[][] grid, int x, int y) {
  22.         if (x < 0 || y < 0) return Integer.MAX_VALUE; // 越界，注意，不是0
  23.         if (f[x][y] >= 0) return f[x][y];
  24.         else return f[x][y] = dfs(grid, x, y);
  25.     }
  26.     private int[][] f;  // 缓存
  27. }

动规

  1. // Minimum Path Sum
  2. // 二维动规
  3. public class Solution {
  4.     public int minPathSum(int[][] grid) {
  5.         final int m = grid.length;
  6.         final int n = grid[0].length;
  7.         if (m == 0) return 0;
  9.         int[][] f = new int[m][n];
  10.         f[0][0] = grid[0][0];
  11.         for (int i = 1; i < m; i++) {
  12.             f[i][0] = f[i - 1][0] + grid[i][0];
  13.         }
  14.         for (int i = 1; i < n; i++) {
  15.             f[0][i] = f[0][i - 1] + grid[0][i];
  16.         }
  18.         for (int i = 1; i < m; i++) {
  19.             for (int j = 1; j < n; j++) {
  20.                 f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
  21.             }
  22.         }
  23.         return f[m - 1][n - 1];
  24.     }
  25. }

动规+滚动数组

  1. // Minimum Path Sum
  2. // 二维动规+滚动数组
  3. public class Solution {
  4.     public int minPathSum(int[][] grid) {
  5.         final int m = grid.length;
  6.         final int n = grid[0].length;
  8.         int[] f = new int[n];
  9.         Arrays.fill(f, Integer.MAX_VALUE); // 初始值是 INT_MAX，因为后面用了min函数。
  10.         f[0] = 0;
  12.         for (int i = 0; i < m; i++) {
  13.             f[0] += grid[i][0];
  14.             for (int j = 1; j < n; j++) {
  15.                 // 左边的f[j]，表示更新后的f[j]，与公式中的f[i[[j]对应
  16.                 // 右边的f[j]，表示老的f[j]，与公式中的f[i-1][j]对应
  17.                 f[j] = Math.min(f[j - 1], f[j]) + grid[i][j];
  18.             }
  19.         }
  20.         return f[n - 1];
  21.     }
  22. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dp/minimum-path-sum.html