有一个大小为 N*M 的迷宫，由单元 block 组成。一开始，爱丽丝有 K 百分比的能量。 现在爱丽丝从第一行开始向第 N 行移动。她可以从当前 block 移动到下一行中的 block ，该 block 位于当前 block 的右侧或左侧。在移动到第 i 行第 j 列的 block 时，如果 C(i,j) 大于 0，她的能量将减少 C(i,j) 百分比，否则它将重新充电 C(i,j) 百分比.
例如，如果她有 50% 的能量，在移动到 C(i,j) = 15 的区 block 时，她将剩余 35 ( 50 -15 )% 的能量。
现在的任务是找出爱丽丝最终的能量状态，如果她以最佳方式移动以节省最大能量。
注意:她的能量不会超过100%，如果她的能量降到0%，她就不会再移动了。
示例:让我们假设一个 4*4 的网格如下:
2 -2 2 -2
-2 2 -2 2
1 -1 1 -1
-1 1 -1 1
如果 K= 10 意味着她在开始时有 10% 的能量。然后在到达第 4 行后，她将拥有 16% 的能量。最佳移动之一是 <1,2> -> <2,1> -> <3,2> -> <4,1>
所以这里的答案是 16。
最佳答案
我最初说你可以自下而上地解决这个问题，但是我将自上而下地手工做这个例子，因为一旦你的能量下降到零你就不能继续的限制 - 它不会'在这里没有用处，但如果你是自上而下的工作，它看起来更容易处理。原理大致相同 - 逐行计算，在每个阶段写下可能遍历每个单元格的最佳分数，使用前一行的答案计算出当前行的答案。
我们从 10 开始，我假设你可以从任何你想要的地方开始，所以只需用 10 减去第一行就可以计算出你能在第一行得到的最好结果，包括你所在的电池的能量差现在在。顶行变为 8, 12, 8, 12。
只能通过一种方式到达下一行的边缘单元格。可以通过两种方式到达内部单元格。在任何一种情况下，我们都会通过考虑该电池的能量差异和您可以从您来自的电池获得的能量来计算那里的总数，当有两个时选择最有希望的选择。所以我们得到 14、10、14、10，例如，第二个 14 是上面和左边或上面的第 12 个之一，右边两个(如果分数不同，我们可以取最好的)与 -2 结合对于那个单元格。
类似地，下一行有 9、15、9、15，底部有 16、8、16、8，例如，到达左下角的唯一方法是从上面的 15 到它的对，所以调整 -1 我们将 15 变成 16。有两种方法可以到达它右边的单元格，但它们都是从 9 开始，所以调整 1 我们得到 8。
如果您需要整个路径，您可以在计算出每个单元格的最佳成本时跟踪您是如何进入每个单元格的，然后在完成时从最佳答案开始向上跟踪。
关于algorithm - 网格中的最佳运动，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21954802/