网格中的递归硬币收集

Question

如何编写一个递归代码，告诉我可以从网格中收集到的硬币的最大数量，在这个网格中，每个单元格可能包含也可能不包含一个只向下和向右移动的硬币？我还得用记忆法。在

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

最大硬币只向下和向右移动=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]

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

因此，首先创建一个2D数组，该数组将包含您在任何单元格中可以拥有的最大硬币数，然后使用递归关系用适当的值填充它。从上一行到下一行，从左到右。在