如何使用动态编程解决此问题

Question

给定一个数字列表，比如[4 5 2 3]，我需要根据以下规则最大化获得的和：

1. 我需要从列表中选择一个数字，该数字将被删除。选择2将使列表为[4503]
2. 如果要删除的数字有两个邻居，那么我应该得到这个选择的结果，作为当前选择的数字与它的一个邻居的乘积，并且这个乘积与另一个邻居相加。例如：如果我选择2，那么我可以得到这个选择的结果为2*5+3
3. 如果我选择一个只有一个邻居的数字，那么结果就是所选数字与其邻居的乘积
4. 当他们只剩下一个数字时，到目前为止，它只是添加到结果中

根据这些规则，我需要按照结果最大化的顺序选择数字。

对于上面的列表，如果选择的顺序是4->2->3->5，则所获得的和为53，这是最大值。

我包括一个程序，它可以让你把元素集作为输入，给出所有可能的和，还可以指示最大和。

这是一个链接。

import itertools
l = [int(i) for i in input().split()]
p = itertools.permutations(l) 
c, cs = 1, -1
mm = -1
for i in p:
var, s = l[:], 0
print(c, ':', i)
c += 1

for j in i:
print(' removing: ', j)
pos = var.index(j)
if pos == 0 or pos == len(var) - 1:
if pos == 0 and len(var) != 1:
s += var[pos] * var[pos + 1]
var.remove(j)
elif pos == 0 and len(var) == 1:
s += var[pos]
var.remove(j)
if pos == len(var) - 1 and pos != 0:
s += var[pos] * var[pos - 1]
var.remove(j)
else:
mx = max(var[pos - 1], var[pos + 1])
mn = min(var[pos - 1], var[pos + 1])

s += var[pos] * mx + mn
var.remove(j)

if s > mm:
mm = s
cs = c - 1
print(' modified list: ', var, 'n  sum:', s)
print('MAX SUM was', mm, ' at', cs)

Answer 1

考虑问题的4种变体：每个元素都被消耗的变体，以及左元素、右元素或右元素和左元素都没有消耗的变体。

在每种情况下，您都可以考虑删除最后一个元素，这将问题分解为1或2个子问题。

这在O(n^3(时间内解决了问题。这里有一个python程序来解决这个问题。solve_的4个变体对应于没有、一个或另一个、或者两个端点都是固定的。毫无疑问，这个程序可以减少(有很多重复(。

def solve_00(seq, n, m, cache):
key = ('00', n, m)
if key in cache:
return cache[key]
assert m >= n
if n == m:
return seq[n]
best = -1e9
for i in range(n, m+1):
left = solve_01(seq, n, i, cache) if i > n else 0
right = solve_10(seq, i, m, cache) if i < m else 0
best = max(best, left + right + seq[i])
cache[key] = best
return best

def solve_01(seq, n, m, cache):
key = ('01', n, m)
if key in cache:
return cache[key]
assert m >= n + 1
if m == n + 1:
return seq[n] * seq[m]
best = -1e9
for i in range(n, m):
left = solve_01(seq, n, i, cache) if i > n else 0
right = solve_11(seq, i, m, cache) if i < m - 1 else 0
best = max(best, left + right + seq[i] * seq[m])
cache[key] = best
return best
def solve_10(seq, n, m, cache):
key = ('10', n, m)
if key in cache:
return cache[key]
assert m >= n + 1
if m == n + 1:
return seq[n] * seq[m]
best = -1e9
for i in range(n+1, m+1):
left = solve_11(seq, n, i, cache) if i > n + 1 else 0
right = solve_10(seq, i, m, cache) if i < m else 0
best = max(best, left + right + seq[n] * seq[i])
cache[key] = best
return best
def solve_11(seq, n, m, cache):
key = ('11', n, m)
if key in cache:
return cache[key]   
assert m >= n + 2
if m == n + 2:
return max(seq[n] * seq[n+1] + seq[n+2], seq[n] + seq[n+1] * seq[n+2])
best = -1e9
for i in range(n + 1, m):
left = solve_11(seq, n, i, cache) if i > n + 1 else 0
right = solve_11(seq, i, m, cache) if i < m - 1 else 0
best = max(best, left + right + seq[i] * seq[n] + seq[m], left + right + seq[i] * seq[m] + seq[n])
cache[key] = best
return best
for c in [[1, 1, 1], [4, 2, 3, 5], [1, 2], [1, 2, 3], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]:
print(c, solve_00(c, 0, len(c)-1, dict()))