如何将以下递归dp转换为迭代
如何将以下递归dp转换为迭代
提问于 2016-02-25 19:33:34
我试图将以下递归代码转换为自下而上/迭代动态规划。但是，由于状态依赖于下一个和以前的索引，我无法确定应该迭代的顺序。
matrix = [[-1, 4, 5, 1],
[ 2,-1, 2, 4],
[ 3, 3,-1, 3],
[ 4, 2, 1, 2]]
rows = len(matrix)
cols = len(matrix[0])
cache = {}
def maxsum(dir, x, y):
key = (dir, x, y)
if key in cache: return cache[key]
base = matrix[y][x]
if x < cols-1:
best = base + maxsum(2, x+1, y)
else:
best = base
if dir != 0 and y > 0:
best = max(best, base + maxsum(1, x, y-1))
if dir != 1 and y < rows-1:
best = max(best, base + maxsum(0, x, y+1))
cache[key] = best
return best是否有可能将此代码转换为迭代？如果是，请帮助我完成迭代的排序。
“‘dir”可以取0-2的值。
X和y在1到1000之间。
我不想用堆栈来解决这个问题。我想用一般的迭代循环来解决这个问题，就像我们在自下而上的动态规划中所做的那样。
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-02-25 22:37:49
其一般思想是想象递归调用图/树以及叶节点是什么；然后，迭代求解简单地从叶节点开始，迭代地构建树，一直到根。
当然，这是说起来容易做起来难，但往往有结构的问题，可以帮助你的直觉。在这种情况下，这是2D网格。
直觉
让我们从建立一些直觉开始。查看代码中的分支。他们决定你是否在特定的情况下进行反悔。它们对应的是什么？，您什么时候不回复？，按顺序排列，这些是：
- 网格的右侧
- 网格的顶部边缘
- 网格的底部边缘
我们得先建造这些。
基箱
扪心自问：，在什么情况下，我们根本不反悔？这是基本情况。没有特别的顺序，这些顺序是：
- 网格的右上角和
dir=1。 - 网格的右下角和
dir=0。
递归案例
最后，问问自己：从我们拥有的值开始，我们可以计算什么？
- 对于右上角，我们可以计算出
dir=1的整个右边沿。 - 对于右下角，我们可以计算
dir=0的整个右边。
这样，我们就可以计算出dir=2的整个右边。
现在我们已经填充了右边边的值，那么我们可以计算什么呢？记住上面的特殊情况。仅依赖于右侧边缘的单元格是位于右侧边缘左侧的顶部和底部边缘的两个单元格，分别使用dir=1和dir=0。
有了这一点，我们现在可以从右边为dir=1和dir=0计算第二列，从而计算dir=2。
重复，直到找到您想要的单元格的值为止。
“守则”
注意:这有点不太理想，因为它填充了整个表，但是它应该足以说明这个想法。
def fill(dir, x, y):
base = matrix[y][x]
if x < cols-1:
best = base + cache[2, x + 1, y]
else:
best = base
if dir != 0 and y > 0:
best = max(best, base + cache[1, x, y - 1])
if dir != 1 and y < rows - 1:
best = max(best, base + cache[0, x, y + 1])
cache[dir, x, y] = best
def maxsum(dir, x, y):
for i in range(cols - 1, -1, -1):
for j in range(rows - 1, -1, -1):
fill(0, i, j)
for j in range(rows):
fill(1, i, j)
for j in range(rows):
fill(2, i, j)
return cache[dir, x, y]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35636632
复制相关文章
相似问题
腾讯云开发者
