本文共 757 字，大约阅读时间需要 2 分钟。

题目：

解答：

简单的动态规划：

dp[i][j] = min(dp[i - 1][j] , dp[i][j - 1]) + grid[i][j];

初始化：

 dp[0][0] = grid[0][0];

 dp[i][0] = dp[i - 1][0] + grid[i][0];

代码：

class Solution {  public:	  int minPathSum(vector
   
    
      > &grid) {		  int m = grid.size();		  if (m == 0)			  return 0;		  int n = grid[0].size();		  vector
     
      
        > dp(m, vector
       
        (n));		  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];	  }  };
       
      
     
    
   

转载地址：http://xytsi.baihongyu.com/