LeetCode 64 最小路径和题解

题目大意：给定一个数字矩阵，从左上到右下找一条路径使得所经过的数字之和最小，每次只能向下或者向右移动，最后给出最小值即可。

分析：一道很经典的动态规划问题，也是IOI以前出现过的第一道DP题目，由于每次只能向下或者向右移动，因此满足了无后效性，很容易地就可以给出递推公式：

$dp[i][j]=max(dp[i-1][j], dp[i][j-1]) + grid[i][j]$

源程序：

int minPathSum(vector< vector<int> >& grid) {
 int m = grid.size(), n = grid[0].size();
 int dp[m][n];
 memset(dp, 0x3f3f3f, sizeof(dp));
 dp[0][0] = grid[0][0];
 for(int i = 1; i < m; i++) {
  dp[i][0] = dp[i - 1][0] + grid[i][0];
 }
 for(int i = 1; i < n; i++) {
  dp[0][i] = dp[0][i - 1] + grid[0][i];
 }
 for(int i = 1; i < m; i++) {
  for(int j = 1; j < n; j++) {
   dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  }
 }
 return dp[m - 1][n - 1];
}

LeetCode 64 最小路径和 题解

浏览过的版块

LeetCode 64 最小路径和题解