记忆化之路阵列

我的问题，我设法解决递归，但我希望，对用记忆化更优化的解决方案，但我没有足够的技术知道应该如何在这方面的工作。记忆化之路阵列

问题：

有一个2D阵列具有随机正整数，并且您将得到的移动的随机量。你开始从左上角移动，并且只允许您做出的举动是：左向右下来

您需要结束在底部行和收集尽可能多的，你可以对你的方式。你不能重新访问一个职位。

记忆化是有关存储的价值观和在此基础上对未来的结果，但因为有一个可以采取这么多的路，我该如何使用它？它是甚至memoization，我应该使用或我做了一个错误的猜测:)？

来源

2012-10-07 user1577191

@Radu：标签[算法]意味着确切的语言对于OP来说并不重要，只要描述该算法即可。 – Vlad

这是什么意思？ :) – user1577191

另请参阅[问题＃12712575]（http://stackoverflow.com/questions/12712575/an-interesting-algorithm-need-pseudocode） –

这基本上是一个动态编程问题。由于路径的细节不会影响未来的决策，因此您不必在每一步都考虑所有可能的路径。对于每个细胞，如果你走特定方向并采取特定数量的移动，则需要知道可以收集的最大量。没有别的因素影响你的决定

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被memoized，那么你得到一个相当有效的解决方案，因为可能性的数量是相对有限的。

虽然将它作为一个动态编程问题来处理会让你更有效。

来源

2012-10-07 16:37:22

谢谢你，沃恩，这就是我需要的！ :) – user1577191

@ user1577191：实际上，从一开始工作甚至更好 –

-1

我想问题的描述是错误的。起点是左上角，唯一允许做的动作是：右下。如果这样做，也可以使用memoization，可以使用0代表正确的值，1代表down，然后每个路径可以用二进制字符串表示，然后可以使用数组dp [int（string）]来记忆该值。

来源

2012-10-07 16:08:56

记忆化之路阵列

回答

相关问题