首页 > 代码库 > 64. Minimum Path Sum

64. Minimum Path Sum

Given a m x 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.

 

 1 class Solution { 2 public: 3     int minPathSum(vector<vector<int>>& grid) { 4         if(grid.size() == 0 || grid[0].size() == 0){ 5             return 0; 6         } 7          8         int row = grid.size(); 9         int col = grid[0].size();10         11         int dp[row][col];12         13         dp[0][0] = grid[0][0];14         15         for(int i = 1; i < row; i++){16             dp[i][0] = dp[i-1][0] + grid[i][0];17         }18         19         for(int j = 1; j < col; j++){20             dp[0][j] = dp[0][j-1] + grid[0][j];21         }22         23         for(int i = 1; i < row; i++){24             for(int j =1; j < col; j++){25                 dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) + grid[i][j];26             }27         }28         return dp[row-1][col-1];29     }30 };

 

64. Minimum Path Sum