LeetCode --- Minimum Path Sum

3254 ワード

タイトルリンク
単純な反転
コードを添付:
 1 class Solution {  2 public:  3     int minPathSum(vector<vector<int> > &grid) {  4         int n = (int)grid.size();  5         if (n == 0) return 0;  6         int m = (int)grid[0].size();  7         

 8         for (int i = m-2; i >= 0; i--) grid[n-1][i] += grid[n-1][i+1];  9         for (int i = n-2; i >= 0; i--) grid[i][m-1] += grid[i+1][m-1]; 10         for (int i = n-2; i >= 0; i--) for (int j = m-2; j >= 0; j--) 11             grid[i][j] += min(grid[i+1][j], grid[i][j+1]); 12             

13         return grid[0][0]; 14  } 15 };