python-3.x - 动态规划,创建备忘录表最长稳定子序列
问题描述
我已经研究了很长一段时间的动态编程问题并且被卡住了,所以非常感谢任何帮助。
def lssLength(a, i, j):
aj = a[j] if 0 <= j < len(a) else None
# Implement the recurrence below. Use recursive calls back to lssLength
assert 0 <= i <= len(a)
if i >= len(a) or j >= len(a):
return 0
if aj and abs(a[i] - a[j]) > 1:
return lssLength(a, i+1, j)
if aj is None or (abs(a[i] - a[j]) <= 1 and i != j):
return max(lssLength(a, i+1, j), lssLength(a, i+1, i) + 1)
else:
return lssLength(a, i+1, j)
这是我针对第一个问题的测试用例:
def test_lss_length(self):
# test 1
n1 = lssLength([1, 4, 2, -2, 0, -1, 2, 3], 0, -1)
print(n1)
self.assertEqual(4, n1)
# test 2
n2 = lssLength([1, 2, 3, 4, 0, 1, -1, -2, -3, -4, 5, -5, -6], 0, -1)
print(n2)
self.assertEqual(8, n2)
# test 3
n3 = lssLength([0, 2, 4, 6, 8, 10, 12], 0, -1)
print(n3)
self.assertEqual(1, n3)
# test 4
n4 = lssLength(
[4, 8, 7, 5, 3, 2, 5, 6, 7, 1, 3, -1, 0, -2, -3, 0, 1, 2, 1, 3, 1, 0, -1, 2, 4, 5, 0, 2, -3, -9, -4, -2, -3,
-1], 0, -1)
print(n4)
self.assertEqual(14, n4)
现在我需要采用递归解决方案并将其转换为动态编程,这就是我卡住的地方。我正在使用与以前相同的测试,但测试失败了。
def memoizeLSS(a):
T = {} # Initialize the memo table to empty dictionary
# Now populate the entries for the base case
# Now fill out the table : figure out the two nested for loops
# It is important to also figure out the order in which you iterate the indices i and j
# Use the recurrence structure itself as a guide: see for instance that T[(i,j)] will depend on T[(i+1, j)]
n = len(a)
for i in range(0, n+1):
for j in range(-1, n+1):
T[(i, j)] = 0
for i in range(n-1, -1, -1):
for j in range(n-1, -1, -1):
if abs(a[i] - a[j]) > 1:
try:
T[(i, j)] = max(0, T[(i, j+1)], T[(i+1, j)])
except Exception:
T[(i, j)] = 0
elif abs(a[i] - a[j]) <= 1 and i != j:
T[(i, j)] = T[(i+1, j+1)] + 1
else:
T[(i, j)] = max(0, T[(i+1, j+1)])
for i in range(n-2, -1, -1):
T[(i, -1)] = max(T[(i+1, -1)], T[(i+1, 0)], T[(i, 0)], 0)
return T
如果您已阅读所有这些内容,非常感谢您。我知道这很多,非常感谢您的时间。非常感谢任何指向阅读材料等的指针。如果需要更多详细信息,请告诉我。谢谢。
解决方案
您的解决方案仅适用于第一个测试用例。以下是修正版:
def memoizeLSS(a):
T = {} # Initialize the memo table to empty dictionary
n = len(a)
for j in range(-1, n):
T[(n, j)] = 0 # i = n and j
# Now populate the entries for the base case
# Now fill out the table : figure out the two nested for loops
# It is important to also figure out the order in which you iterate the indices i and j
# Use the recurrence structure itself as a guide: see for instance that T[(i,j)] will depend on T[(i+1, j)]
n = len(a)
for i in range(0, n + 1):
for j in range(-1, n + 1):
T[(i, j)] = 0
for i in range(n-1, -1, -1):
for j in range(n-1, -1, -1):
aj = a[j] if 0 <= j < len(a) else None
if aj != None and abs(a[i] - a[j]) > 1:
T[(i, j)] = T[(i+1, j)]
elif aj == None or abs(a[i] - a[j]) <= 1:
T[(i, j)] = max(T[(i+1, i)] + 1, T[(i + 1, j)])
for i in range(n-2, -1, -1):
T[(i, -1)] = max(T[(i+1, -1)], T[(i+1, 0)], T[(i, 0)], 0)
return T
推荐阅读
- python - Python在并行化任务中包含while循环
- java - Spring Boot中基于角色的授权
- django - ubuntu 中的 Django Bootstrap 模块
- jbase - 导入 t24 版本时设计工作室出错
- reactjs - 为什么我的 Suspense 不显示我延迟加载的组件?
- shell - 我们如何使用 '~|~' 分隔符来使用脚本命令分割记录?
- sql - 根据两行的数据创建一行
- python - 如何在python中的word docx中替换整个xml元素,就好像它们是字符串一样
- graphql - 考虑到 Apollo-Server,一个请求可以发送多少个 GraphQL 突变?
- c++ - 如何在 C 程序中使用 Boost 库