# 最小路径和

<p>给定一个包含非负整数的 <code><em>m</em> x <em>n</em></code> 网格 <code>grid</code> ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。</p><p><strong>说明：</strong>每次只能向下或者向右移动一步。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0064.Minimum%20Path%20Sum/images/minpath.jpg" style="width: 242px; height: 242px;" /><pre><strong>输入：</strong>grid = [[1,3,1],[1,5,1],[4,2,1]]<strong><br />输出：</strong>7<strong><br />解释：</strong>因为路径 1→3→1→1→1 的总和最小。</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>grid = [[1,2,3],[4,5,6]]<strong><br />输出：</strong>12</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>m == grid.length</code></li>	<li><code>n == grid[i].length</code></li>	<li><code>1 <= m, n <= 200</code></li>	<li><code>0 <= grid[i][j] <= 100</code></li></ul>
<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;

    int a = 3, b = 3;
    vector<vector<int>> grid = vector<vector<int>>(a, vector<int>(b)) = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    int res;
    res = sol.minPathSum(grid);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
private:
    int m, n;
    int memo[100][100];

public:
    int minPathSum(vector<vector<int>> &grid)
    {
        m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; i++)
        {
            memset(memo[i], -1, sizeof(int) * n);
        }
        return dfs(grid, 0, 0);
    }

    int dfs(vector<vector<int>> &grid, int r, int c)
    {

        if (r < 0 || r >= m || c < 0 || c >= n)
            return 1000000;

        if (memo[r][c] != -1)
            return memo[r][c];

        if (r == m - 1 && c == n - 1)
        {
            memo[r][c] = grid[m][n - 1];
            return memo[r][c];
        }

        int right = dfs(grid, r, c + 1);
        int down = dfs(grid, r + 1, c);
        memo[r][c] = min(right, down) + grid[r][c];
        return memo[r][c];
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        int row = grid.size();
        int col = grid[0].size();
        vector<int> f(col, 0);

        for (int i = 0; i < row; ++i)
        {
            f[0] = f[0] + grid[i][0];
            for (int j = 1; j < col; ++j)
            {
                if (i == 0)
                    f[j] = f[j - 1] + grid[i][j];
                else
                    f[j] = min(f[j - 1], f[j]) + grid[i][j];
            }
        }
        return f[col - 1];
    }
};
```

### B

```cpp
class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        int row = grid.size();
        int column = grid[0].size();
        for (int i = 1; i < column; ++i)
        {
            grid[0][i] = grid[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < row; ++i)
        {
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < row; ++i)
        {
            for (int j = 1; j < column; ++j)
            {
                int temp = grid[i - 1][j] > grid[i][j - 1] ? grid[i][j - 1] : grid[i - 1][j];
                grid[i][j] = grid[i][j] + temp;
            }
        }
        return grid[row - 1][column - 1];
    }
};
```

### C

```cpp
class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        if (grid.size() == 0)
            return 0;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> m_memo = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

        for (int i = n - 1; i >= 0; --i)
            m_memo[m - 1][i] = grid[m - 1][i] + m_memo[m - 1][i + 1];
        for (int j = m - 1; j >= 0; --j)
            m_memo[j][n - 1] = grid[j][n - 1] + m_memo[j + 1][n - 1];

        for (int i = m - 2; i >= 0; --i)
        {
            for (int j = n - 2; j >= 0; --j)
            {
                m_memo[i][j] = grid[i][j] + min(m_memo[i][j + 1], m_memo[i + 1][j]);
            }
        }
        return m_memo[0][0];
    }
};
```