这道题不就是我在 Unique Paths 里面提到的最短路径问题嘛。不过其实解法和那道题类似，我们还是采取划分子问题的方式来分析：
可以看到，在最后一步的选择中，要么选择从上面下来，要么选择从左边过来，很显然，选择小的那个。那么 DP 公式呼之欲出：
f[i][j] = min(f[i-1][j], [i][j-1]) + grid[i][j];
于是咱们就可以采取和上一道题同样的方式，用DP的思路来进行迭代了。（迭代过程中记录每一步的解）
比那道题要好的一点在于，这次给的是一个 vector，而且采用的是 reference 的方式，很显然，我们根本不需要额外使用空间，只需要将时间复杂度尽量降低即可。
我绘制了一幅图，可以理顺整个流程：
有几个特殊情况要考虑：
- 对于第一格，跳过，因为必选。
- 对于第一行，f[i][j] = grid[i][j] + grid[i][j-1]
- 对于第一列，f[i][j] = grid[i][j] + grid[i-1][j]
- 其余情况下，f[i][j] = min(grid[i][j-1], grid[i-1][j]) + grid[i][j]
然后，几乎代码呼之欲出了。。。