leetcode 64 Minimum Path Sum C++

动态规划

状态转移方程 dp[i][j] += min(dp[i-1][j],dp[i][j-1])

一次AC，代码如下：

int minPathSum(vector<vector<int>>& grid) { int row = grid.size(); int col = grid[0].size(); for (int i = 1;i<row;i++) { grid[i][0] += grid[i-1][0]; } for (int i = 1;i<col;i++) { grid[0][i] += grid[0][i-1]; } for (int i = 1;i<row;i++) for (int j = 0;j<col;j++) { grid[i][j] += min(grid[i-1][j],grid[i][j-1]); } return grid[row-1][col-1]; }