题目链接：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.

这道题的要求是在m*n的网格中找到从左上角到右下角的和最小的路径。每次只能向下或者向右移动1格。

这是动态规划的问题，由于每次只能向下或者向右移动，因此[i, j]位置时的最小路径的和等于[i, j-1]和[i-1, j]中较小的加上[i, j]位置的数值。因此递推公式是grid[i][j] += min(grid[i][j-1], grid[i-1][j])。

时间复杂度：O(mn)

空间复杂度：O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution
{
public:
    int minPathSum(vector<vector<int> > &grid)
    {
        
        if(grid.size() == 0 || grid[0].size() == 0)
            return 0;
        
        for(int i = 0; i < grid.size(); ++ i)
            for(int j = 0; j < grid[i].size(); ++ j)
            {
                if(i == 0 && j == 0) // 左上角的点不做处理
                    continue;
                else if(i == 0) // 处理左面边界
                    grid[i][j] += grid[i][j - 1];
                else if(j == 0) // 处理上面边界
                    grid[i][j] += grid[i - 1][j];
                else
                    grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        
        return grid[grid.size() - 1][grid[0].size() - 1];
    }
};