遇到一个矩阵最小路径和的问题，求解答。
给定一个矩阵，大小为 m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置。路径中所有数字累加起来就是路径和，返回所有路径的最小路径和。
展开
收起
1
条回答
写回答
写回答
-
本题可以用动态规划的方法来解决。计算一个格子到右下角的最小路径需要两个数据，一个是右边格子到右下角的最小路径，一个是下边格子到右下角的最小路径，两个数据的较小值加上当前格子的数值即为最小路径。即dp[i, j]=min(dp[i+1,j],dp[i, j+1])+m[i,j] 由于计算当前格子最小路径需要右边和下边格子的最小路径。因此，需要从底向 上进行决策。本题用动态规划法的难点之一是从底向上进行决策的顺序。如下图所示，通过观察可以发现，同一对角线上的数字的横纵坐标和是相等的，我们以对角线的方向为顺序，从右下角向左上角计算出每个格子的最小路径。最后可计算得出dp[0,0]。
比如输入矩阵为 4 1 5 3 3 2 7 7 6 5 2 8 8 9 4 5 最小路径为232021-12-23 18:32:16赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
