java - 从二维数组中找到最低的总和路径

Question

仅考虑下面的一种算法就是针对该算法的陈述

给定一个矩阵，每个节点都有一个值。您从 0,0 开始，必须到达 n,m。从 i,j 可以转到 i+1,j 或 i,j+1。当您踏上每个积木时，该积木上的值将添加到您的当前分数中。您必须携带的最低初始分数是多少，以便您始终可以到达 n,m(通过任何可能的路径)并最终获得正分数。

例如:

Matrix ->        2   3   4
                -5  -6   7
                 8   3   1

Ans -> 6 – 对于路径 2,-5,-6,3,1，我们需要初始分数为 6，这样当我们到达 1 时，我们的分数为 1

所以我可以使用蛮力和动态编程来做到这一点，但仍在思考可能比这更好的方法，请分享您的想法，只是想法/想法我不需要实现，因为我可以做到这一点。

Answer 1

有很多搜索算法，我鼓励你阅读这些维基百科页面:

https://en.wikipedia.org/wiki/Pathfinding

https://en.wikipedia.org/wiki/Tree_traversal

一种可能的解决方案是将数组转换为图形并对其应用最短路径算法，另一种解决方案是使用一些 IA 算法，例如 A*。

A*(发音为 A 星)的维基百科链接:

https://en.wikipedia.org/wiki/A*_search_algorithm