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. class Solution {
  4. public:
  5.     int minPathSum(vector<vector<int> > &grid) {
  6.         const int m = grid.size();
  7.         const int n = grid[0].size();
  8.         this->f = vector<vector<int> >(m, vector<int>(n, -1));
  9.         return dfs(grid, m-1, n-1);
  10.     }
  11. private:
  12.     vector<vector<int> > f;  // 缓存
  14.     int dfs(const vector<vector<int> > &grid, int x, int y) {
  15.         if (x < 0 || y < 0) return INT_MAX; // 越界，终止条件，注意，不是0
  17.         if (x == 0 && y == 0) return grid[0][0]; // 回到起点，收敛条件
  19.         return min(getOrUpdate(grid, x - 1, y),
  20.                 getOrUpdate(grid, x, y - 1)) + grid[x][y];
  21.     }
  23.     int getOrUpdate(const vector<vector<int> > &grid, int x, int y) {
  24.         if (x < 0 || y < 0) return INT_MAX; // 越界，注意，不是0
  25.         if (f[x][y] >= 0) return f[x][y];
  26.         else return f[x][y] = dfs(grid, x, y);
  27.     }
  28. };

动规

  1. // Minimum Path Sum
  2. // 二维动规
  3. class Solution {
  4. public:
  5.     int minPathSum(vector<vector<int> > &grid) {
  6.         if (grid.size() == 0) return 0;
  7.         const int m = grid.size();
  8.         const int n = grid[0].size();
  10.         int f[m][n];
  11.         f[0][0] = grid[0][0];
  12.         for (int i = 1; i < m; i++) {
  13.             f[i][0] = f[i - 1][0] + grid[i][0];
  14.         }
  15.         for (int i = 1; i < n; i++) {
  16.             f[0][i] = f[0][i - 1] + grid[0][i];
  17.         }
  19.         for (int i = 1; i < m; i++) {
  20.             for (int j = 1; j < n; j++) {
  21.                 f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
  22.             }
  23.         }
  24.         return f[m - 1][n - 1];
  25.     }
  26. };

动规+滚动数组

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

相关题目

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