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

���������������������������������������

������������

������������������ $m \times n$ ���������������������������������������������������������������������������������������������������������������������������������������������������������������������

������������

������������������������������������������������DP������������������������������������������������������������ dp��������� dp[i][j] ������������������������������������������ $(i,j)$ ���������������������

���������������

������������������

���������������������������������������������������������������������������������������������������

������������

���������������������������������������������������������������������������������������������������������������������������������������������

������������

#include 
   
    
using namespace std;
class Solution {
public:
    int minPathSum(vector
    
     
      > grid) {
        int len1 = grid.size();
        int len2 = grid[0].size();
        vector
      
       
        > dp(len1, vector
        
         (len2, 0)); dp[0][0] = grid[0][0]; // ��������������������������� for (int i = 1; i < len1; ++i) { dp[i][0] = dp[i-1][0] + grid[i][0]; } for (int j = 1; j < len2; ++j) { dp[0][j] = dp[0][j-1] + grid[0][j]; } // ������������������ for (int i = 1; i < len1; ++i) { for (int j = 1; j < len2; ++j) { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } return dp[len1-1][len2-1]; } };
        
       
      
     
    
   

������

������������������������������������������������������������������������������������������������������������������������������������������������ $O(mn)$������������������������ $O(mn)$������������������������������������