1

The problem I have, I managed to solve recursively, but I wish for a more optimal solution that would use memoization, but I am not skilled enough to know how it should work in this context.

The problem:

There is an 2d array with random positive integers, and you are given a random amount of moves. You start moving from the top left corner, and the only moves you are allowed to make are: left right down

You need to end at the bottom row and collect as much as you can on your way. You cannot revisit a position.

Memoization is about storing values and building the future results on this, but since there are so many paths one can take, how do I use it? Is it even memoization that I should use or have I made a wrong guess :) ?

4

2 に答える 2

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 がメモ化されている場合、可能性の数が比較的限られているため、かなり効率的なソリューションが得られます。

ただし、動的プログラミングの問題として扱うと、さらに効率的なソリューションが得られます。

于 2012-10-07T16:37:22.040 に答える
-1

問題の説明が間違っていると思います。開始点は左上隅で、実行できる移動は次のとおりです。右下。これなら、メモ化もできて、右を0、下を1にして、すべてのパスをバイナリ文字列で表現し、配列dp[int(string)]を使って値を記憶することができます。

于 2012-10-07T16:08:56.473 に答える