algorithm - 记忆和路径数组

Question

我遇到的问题，我设法递归解决，但我希望有一个更优化的解决方案，可以使用记忆，但我不够熟练，不知道它应该如何在这种情况下工作。

问题：

有一个带有随机正整数的 2d 数组，并且给你随机的移动量。您从左上角开始移动，您可以进行的唯一移动是：左右下

您需要在最后一行结束并在途中收集尽可能多的东西。您不能重新访问某个职位。

记忆是关于存储值并在此基础上构建未来的结果，但是由于可以采取的路径很多，我该如何使用它呢？我应该使用它甚至是记忆还是我猜错了:)？

Answer 1

这基本上是一个动态规划问题。您实际上不必在每一步都考虑所有可能的路径，因为路径的细节不会影响未来的决策。对于每个单元格，您需要知道如果您朝特定方向移动并采取特定数量的移动，则可以收集的最大数量。没有其他任何东西会影响您的决定。

def bestAmount(x,y,direction,n_moves):
  # If this position is off the grid, then this isn't a valid state
  if x<0 or x>=width or y>=height:
    return None
  if n_moves==0:
    # We came to the last move.
    if y!=height-1:
      # If we're not at the bottom row then this isn't a valid path.
      return None
    # Otherwise, the final cell value is part of our total.
    return cellValue(x,y)
  if direction=='down':
    # If we came down to get to this position, then the next move
    # can be either  left, right, or down
    left = bestAmount(x-1,y,'left',n_moves-1)
    right = bestAmount(x+1,y,'right',n_moves-1)
    down = bestAmount(x,y+1,'down',n_moves-1)
    return max(left,right,down)+cellValue(x,y)
  if direction=='left':
    # If we moved left to get to this position, then
    # we can't go right, since we would be visiting the same position again.
    left = bestAmount(x-1,y,'left',n_moves-1)
    down = bestAmount(x,y+1,'down',n_moves-1)
    return max(left,down)+cellValue(x,y)
  if direction=='right':
    # same logic as for left, but opposite.
    right = bestAmount(x+1,y,'right',n_moves-1)
    down = bestAmount(x,y+1,'down',n_moves-1)
    return max(right,down)+cellValue(x,y)

def solve(n_moves):
  # Start by pretending we entered the starting cell by going down
  return bestAmount(0,0,'down',n_moves)

如果 bestAmount 被记忆，那么你会得到一个相当有效的解决方案，因为可能性的数量是相对有限的。

Treating it as a dynamic programming problem will get you an even more efficient solution though.

Answer 2

我想问题的描述有问题。起点在左上角，唯一允许的动作是：右下角。如果这样，也可以做memoization，可以用0代表右，1代表下，那么每条路径都可以用二进制字符串表示，然后可以用数组dp[int(string)]来记忆值。