题目

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

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

示例:

输入:

1
2
3
4
5
[
  [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)为该节点的值。那么可以得到

1
2
3
4
5
6
7
8
9
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)
 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
26
27
/**
 * @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)?动态规划的意义是什么? - 阮行止的回答 - 知乎