# 题目

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

**输入**:
```
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
```
**输出**: 7
**解释**: 因为路径 1→3→1→1→1 的总和最小。

# 题解

设`f(m, n)`为`(0, 0) -> (m, n)`最小的路径和, `v(m, n)`为该节点的值。那么可以得到

```
f(n, n) = min{f(n-1, n), f(n, n-1)} + v(n, n)
f(0, 0) = v(0, 0) = 1
f(0, 1) = min{f(0, 0)} + v(0, 1) = 4
f(1, 0) = 2
f(1, 1) = min(f(0, 1), f(1, 0)) + v(1, 1) = 7

...

f(m, n) = min(f(m-1, n), f(m, n-1)) + v(m, n)
```

```go
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const f = Array.from(new Array(m), x => new Array());

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const v = grid[i][j];
      let d = Infinity;
      if (i + j === 0) {
        d = grid[i][j];
      }
      if (i - 1 >= 0) {
        d = Math.min(d, f[i-1][j] + v);
      }
      if (j - 1 >= 0) {
        d = Math.min(d, f[i][j-1] + v);
      }
      f[i][j] = d;
    }
  }
  return f[m-1][n-1];
};
```

# 参考资料
> [什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 阮行止的回答 - 知乎] (https://www.zhihu.com/question/23995189/answer/613096905)


最小路径和

题目

题解

参考资料