如何使用动态规划解决这个问题？

Question

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

我需要 select 列表中的一个号码，该号码将被删除。例如。 selecting 2 的列表为 [4 5 3]。
如果要删除的数字有两个邻居，那么我应该得到这个 selection 的结果作为当前 selected 数字与其邻居之一的乘积和该乘积的总和和另一个邻居在一起。例如：如果我 select 2 那么我可以将此选择的结果作为 2 * 5 + 3.
如果我 select 一个数字只有一个邻居，那么结果是 selected 数字与其邻居的乘积。
当他们只剩下一个数字时，就把它加到结果中，直到现在。

按照这些规则，我需要 select 以结果最大化的顺序排列数字。

对于上面的列表，如果选择的顺序是4->2->3->5，那么得到的总和是53，这是最大值。

我提供了一个程序，它允许您将元素集作为输入传递并给出所有可能的总和，还指示最大总和。

这里是a link。

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 个变体对应于 none，一个或另一个，或两个端点被固定。毫无疑问，这个程序可以减少（有很多重复）。

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()))

如何使用动态规划解决这个问题？

How can I solve this problem using dynamic programming?

algorithm

math

optimization

memoization

dynamic-programming