我正在学习一些算法和 DS，遇到了一个 DP 问题。寻找一些提示。这是声明:
Given a mxn grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
请提示!
我想过一些事情，但它们就是行不通。这没有意义，因为我最初的想法是，
使用 dp[i][j] 进行内存，其中 dp[i][j] 是 i*j 网格的最小路径总和。这没有意义，因为我不确定如何从中获得 do[i + 1][j + 1]。
这个想法是否正确。你能推荐点什么吗？
最佳答案
初始化角单元，即 dp[0][j] 和 dp[i][0]。然后对于任何 dp[i][j]，遍历该路径的成本将为 val[i][j] + min(dp[i-1][j-1 ], dp[i-1][j], dp[i][j-1]).
dp[row][col] 应该有最小路径的代价。您还可以使用 dp[][] 回溯并找到最小成本路径。
祝你好运。
关于algorithm - 动态规划 m*n 网格最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45101525/