最小路径和

 1int minPathSum(vector<vector<int>>& grid)
 2{
 3    int r = grid.size(), c = grid[0].size();
 4    int dp[r][c];
 5    dp[0][0] = grid[0][0];
 6    for(int i = 1; i < r; i++) dp[i][0] = grid[i][0] + dp[i - 1][0];
 7    for(int i = 1; i < c; i++) dp[0][i] = grid[0][i] + dp[0][i - 1];
 8
 9    for(int i = 1; i < r; i++)
10    {
11        for(int j = 1; j < c; j++)
12        {
13            dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
14        }
15    }
16    return dp[r - 1][c - 1];
17}

 1int minPathSum(vector<vector<int>>& grid)
 2    {
 3        if(grid.empty()) return 0;
 4        int m = grid.size(), n = grid[0].size();
 5        std::vector<int> dp(n, 0);
 6
 7        // 初始化第一行
 8        dp[0] = grid[0][0];
 9        for(int i = 1; i < n; i++)
10        {
11            dp[i] = dp[i - 1] + grid[0][i];
12        }
13
14        // 填充其余行
15        for(int i = 1; i < m; i++)
16        {
17            // 先更新每行第一个元素
18            dp[0] += grid[i][0];
19            for(int j = 1; j < n; j++)
20            {
21                dp[j] = std::min(dp[j], dp[j - 1]) + grid[i][j];
22            }
23        }
24        return dp[n - 1];
25    }