这道题不就是我在 Unique Paths 里面提到的最短路径问题嘛。不过其实解法和那道题类似，我们还是采取划分子问题的方式来分析：

可以看到，在最后一步的选择中，要么选择从上面下来，要么选择从左边过来，很显然，选择小的那个。那么 DP 公式呼之欲出：

f[i][j] = min(f[i-1][j], [i][j-1]) + grid[i][j];

于是咱们就可以采取和上一道题同样的方式，用DP的思路来进行迭代了。（迭代过程中记录每一步的解）

比那道题要好的一点在于，这次给的是一个 vector，而且采用的是 reference 的方式，很显然，我们根本不需要额外使用空间，只需要将时间复杂度尽量降低即可。

我绘制了一幅图，可以理顺整个流程：

有几个特殊情况要考虑：

然后，几乎代码呼之欲出了。。。