问题概述:你是一个松露收集者，给你一个数字网格，代表有松露的地块。每块地里都有一定数量的松露。你必须找到从网格顶部到底部(收集最多松露的那个)的最佳路径。重要的是，您可以从顶部行的任何单元格开始。当您在单元格处时，您可以向左、直接向下或向右对角线向下移动。块菌田可能是这样的:
松露地也不必是方形的。它们可以有任意维度
因此，我为这个问题创建了一个迭代算法。本质上，我所做的就是遍历最上面一行的每个单元格，找到从每个单元格出发的贪婪路径，然后选择松露产量最大的那个。更详细地说，贪心路径是在每一步中，从当前单元格的下一行中选择可以到达的最大值的路径。
对于某些松露字段，该算法会产生正确的结果，如上面的字段，但对于像这样的字段，它会失败:
这是因为当算法到达第三列的100时，它将直接向下移动到3，因为3是它可以移动到的最大的即时值，但它没有考虑移动到它左边的2就可以达到另一个100。通过这个字段的最优路径显然涉及两个值为100的单元格，但是我现在的贪婪算法永远不会产生这个路径。
所以，我有一种预感，这个问题的正确算法涉及递归，特别是递归回溯，但我不确定如何创建递归算法来解决它。我一直在与递归作斗争，发现很难想出使用它的算法。我将非常感谢你们提供的任何建议。
下面是代码。我的算法正在findPath方法中执行:https://github.com/jhould007/Programming-Assignment-3/blob/master/Truffle.java.
您可以使用递归，但是您的方法也有一个简单的迭代修复。
- 从最下面一行开始，而不是最上面一行。创建一个1D数组
values，并使用底部行的值初始化它。 - 开始从
max_row-1行到0行迭代curr_row。对于每次迭代，创建一个临时数组temp并使用0's初始化它。 - 对于迭代中的
curr_row行，value[i]表示从curr_row+1行(基本上是下一行)和i列开始可以得到的最大值。 - 为了在每次迭代中更新
temp，我们只需要从下一行中选择最佳路径，该路径可以从values数组中获取。
for column in range [0, max_column]:
temp[column] = truffle_value[column] + max(value[column], value[column+1], value[column-1])
// since temp holds the values for the next iteration in our loop
value = temp
最后，答案将是max(values)。