dynamic-programming - 这个最优子结构方程正确吗？

Question

给定填充有非负数的 amxn 网格，找到一条从右下角到左上角的路径，该路径最小化沿其路径的所有数字的总和。

我们从右下角或 (m,n) 开始，我们的目标是到达位置 (1,1) 或左上角。

我只是有点困惑，我不知道我是否正确自上而下的方法是最佳子结构如下吗？

CostToMove(i,j) = Min(CostToMove(i-1,j), CostToMove (i, j+1)) + Cost(i,j)

标签： dynamic-programming

Answer 1

你似乎有很好的方法。您需要解决一个小问题：CostToMove (i, j+1). 在这里你是向右走而不是向左走，所以我猜你想说CostToMove (i, j-1)