动态规划解决方案：通过放置括号来最大化表达式

Question

我正在尝试实现Coursera上的算法工具箱课程中的算法，该算法接受算术表达式（如5+8*4-2）并计算其可能的最大值。然而，我不太理解所示算法最后一部分中索引的选择；我的实现无法使用在两个表格中初始化的值来计算值（这些值用于存储子表达式的最大化和最小化值）。

evalt函数只是获取字符，将其转换为操作数并计算两个数字的乘积：

def evalt(a, b, op):
    if op == '+':
        return a + b
#and so on

MinMax计算子表达式的最小值和最大值

def MinMax(i, j, op, m, M):
    mmin = 10000
    mmax = -10000
    for k in range(i, j-1):
        a = evalt(M[i][k], M[k+1][j], op[k])
        b = evalt(M[i][k], m[k+1][j], op[k])
        c = evalt(m[i][k], M[k+1][j], op[k])
        d = evalt(m[i][k], m[k+1][j], op[k])
        mmin = min(mmin, a, b, c, d)
        mmax = max(mmax, a, b, c, d)
    return(mmin, mmax)

这是主函数的主体部分

def get_maximum_value(dataset):
    op = dataset[1:len(dataset):2]
    d = dataset[0:len(dataset)+1:2]
    n = len(d)
    #iniitializing matrices/tables
    m = [[0 for i in range(n)] for j in range(n)]  #minimized values
    M = [[0 for i in range(n)] for j in range(n)]  #maximized values
    for i in range(n):
        m[i][i] = int(d[i])   #so that the tables will look like
        M[i][i] = int(d[i])   #[[i, 0, 0...], [0, i, 0...], [0, 0, i,...]]
    for s in range(n):   #here's where I get confused
        for i in range(n-s):
            j = i + s
            m[i][j], M[i][j] = MinMax(i,j,op,m,M)
    return M[0][n-1]

- Elen

---

你有什么问题？它在做什么或者没有做什么，让你不理解？ - aghast

我假设MinMax函数存在某种故障，因为它未正确填充表m和M。 - Elen

你需要再解释一下。我没有学过那门课，也不知道你的代码想要做什么。我看到了很多零，所以我怀疑它并没有做太多事情，因为a+0、a-0、a*0这些表达式并不是很有趣。你能解释一下你的代码意图吗？值应该是什么？可以给出一些输入和期望输出的例子吗？ - aghast

Answer 1

很抱歉打扰您，这里需要改进的内容如下：

for s in range(1,n)

在主函数中，以及。

for k in range(i, j):

在MinMax函数中。现在它可以工作了。

- Elen

---

谢谢@Elen..这帮了很多。希望你的NLP研究进展顺利。 - aRise

Answer 2

以下更改应该有效。

 for s in range(1,n):
    for i in range(0,n-s):

- Maaz Ahmed

---

虽然这可能回答了作者的问题，但它缺少解释性的文字和链接到文档。原始代码片段没有周围的一些短语并不是很有帮助。请编辑您的答案。 - hellow

这也是对一个两年前问题的回答。另外，欢迎来到 SO :) - hellow