algorithm - 大括号表达式的最大结果 - 算法

Question

我的表达式由用加号和减号分隔的数字组成。我需要通过在数字之间放置大括号来获得此表达式的最大结果。我正在尝试为这个问题获得多项式算法，但我需要一些建议或提示如何实现它。我发现了类似的东西 here , 但我不知道如何修改它。

编辑:我在想这个想法可以像这样类似

getMax(inp)
{ 
  if(|inp| == 1) 
    return inp[1] // base case 
  else
    val = 0;
    for(k=2; k < |inp|; k+=2)
        val = max{val, getMax(inp[:k]) + getMax(inp[k+1:])} 
}

Answer 1

一种策略是使用动态规划来选择最后执行的最佳操作。这将表达式分为两部分。

如果操作是加法，则递归调用每个部分以找到每个部分的最大值。

如果运算是减法，你想在第一部分找到最大值，在第二部分找到最小值。

这里是一些非内存代码，只是为了展示递归是如何工作的(注意 i 只在操作的索引上迭代，以选择中断表达式的最佳位置):

import re

def T(s, f1=max, f2=min):
    if len(s) == 1: 
        return int(s[0])

    return f1(
           T(s[:i], f1, f2)+T(s[i+1:], f1, f2) 
           if s[i]=='+' else
           T(s[:i], f1, f2)-T(s[i+1:], f2, f1) 
           for i in xrange(1, len(s), 2))

def solve(expr):
    return T(re.split('([+-])', expr))

print solve('1-2+1') #0 ((1-2)+1)
print solve('1-22-23') #2 (1-(22-23))

实现自下而上的动态规划有点棘手，因为填充表格的理想顺序有些不同寻常。最简单的方法是使 DP 围绕 T(k, i) 表示“从 i 开始的 k 操作数表达式的最大值/最小值>第一个操作数”。使用 Anonymous 的想法，分别在 O 和 N 中分隔运算符和数字，示例代码为:

import re

def T(O, N):
    n1 = len(N)+1 #maximum expression length

    Tmax = [[float('-Inf')]*len(N) for _ in xrange(n1)]
    Tmin = [[float('+Inf')]*len(N) for _ in xrange(n1)]

    for i, n in enumerate(N): #only the numbers
        Tmax[1][i] = Tmin[1][i] = int(n)

    for k in xrange(2, n1):
        for i in xrange(n1-k):
            for j in xrange(1, k):
                if (O[i+j-1] == '+'):
                    Tmax[k][i] = max(Tmax[k][i], Tmax[j][i]+Tmax[k-j][i+j])
                    Tmin[k][i] = min(Tmin[k][i], Tmin[j][i]+Tmin[k-j][i+j])
                else:
                    Tmax[k][i] = max(Tmax[k][i], Tmax[j][i]-Tmin[k-j][i+j])
                    Tmin[k][i] = min(Tmin[k][i], Tmin[j][i]-Tmax[k-j][i+j])

    return Tmax[len(N)][0]

def solve(expr):
    A = re.split('([+-])', expr)
    return T(A[1::2], A[::2])

print solve('1+1') #2
print solve('1-2+1') #0 ((1-2)+1)
print solve('1-22-23') #2 (1-(22-23))