网格中的递归收集硬币

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]

如果你按照这个递归关系来编程，会发现很多不同单元格的相同参数调用会重复，这样计算的复杂度会变得很高，甚至是指数级的。为了避免这种情况，你可以把中间计算的结果存储在一个数组里，当需要再次使用时直接取出来。这样，你只需要计算每个单元格的值一次，代码运行起来会快很多。

所以，首先创建一个二维数组，用来存放每个单元格能获得的最大硬币数量，然后根据递归关系填充这个数组的值。记得从上到下、从左到右依次进行填充。