python - 在网格中递归收集硬币

Question

如何编写递归代码来告诉我可以从网格中收集的硬币的最大数量，其中每个单元格可能包含也可能不包含仅向下和向右移动的硬币？我还必须使用内存。

ex:  [[0,0,1],
      [0,1,1],
      [1,0,0]]

仅向下和向右移动的 max_coins = 2

Answer 1

首先，您需要这个问题背后的递推关系:如果单元格[i][j]中的最大硬币数量由C[i][j]表示，然后

C[i][j] = max(C[i - 1][j], C[i][j - 1]) + No. of coins on cell[i][j]

如果您使用这种递归进行编码，对于不同的单元格，具有相同参数的相同调用将会有很多重叠，并且其复杂性将呈指数级增长。为了避免这种情况，您可以将中间调用的结果存储在数组中，并在再次需要时使用它们。这样，您只需计算一个单元格的值一次，并且代码会快得多。

因此，首先创建一个二维数组，其中包含任何单元格中可以拥有的最大硬币数量，然后使用递归关系将其填充为适当的值。从顶行到底部，从左到右。