algorithm - 动态编程 spoj 证明 LISA

Question

我试图解决 https://www.spoj.com/problems/LISA/

在问题中，给出的表达式只有 * 和 +。放置括号最大值需要输出。

喜欢

 1+2*3+4*5 = (1+2)*(3+4)*5 = 105

 2*0*3+7+1*0*3 = 2*((0*3+7+1*0)*3) = 42

我遇到的二维动态问题求解方法的实现如下。取每个数字是矩阵行和列并从下到上的方法。

f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )

Like 3,5 =  Max of [  (3,4) * (5,5) or (3,3)+(4,5) ]
         =  Max of [   7*5  or 3+20 ] 
         =  Max of [ 35,23 ] = 35

我无法证明我得到的结果是最大和正确的。如何证明下面的解是最大且最优的？

-----------------------------------
      C1   C2   C3   C4    C5
C1     1    3    9   13    105
C2          2    6   14    70
C3               3   7     35
C4                   4     20
C5                         5

Answer 1

这是我的实现:(它假定查询格式正确)

class LISASolver:
    def solve(self, query):
        """
        takes a query, a string with numbers and +, *,
        returns a tuple of min, max
        """
        numbers, operators = self.parse_inputs(query)
        n = len(numbers)
        self.numbers = numbers
        self.operators = operators
        self.memo = {}
        out = self.dp(0, len(numbers) - 1)
        return out

    def dp(self, i, j):
        if i == j:
            n = self.numbers[i]
            return n, n

        if (i, j) in self.memo:
            return self.memo[(i, j)]

        curmins = []
        curmaxs = []
        for k in range(i, j):
            o = lambda a, b: (a * b) if self.operators[k] == '*' else (a + b)
            leftmin, leftmax = self.dp(i, k)
            rightmin, rightmax = self.dp(k + 1, j)
            curmins.append(o(leftmin, rightmin))
            curmaxs.append(o(leftmax, rightmax))
        self.memo[(i, j)] = (min(curmins), max(curmaxs))

        return self.memo[(i, j)]

    def parse_inputs(self, query):
        numbers = []
        operators = []
        current_number = []

        for c in query:
            if c.isdigit():
                current_number.append(c)
            else:
                numbers.append(
                    int(''.join(current_number))
                )
                current_number = []
                operators.append(c)

        numbers.append(
            int(''.join(current_number))
        )
        return numbers, operators

s = LISASolver()
query = '1+2*3+4*5'
print(s.solve(query))
>>> 27, 105
query = '2*0*3+7+1*0*3'
print(s.solve(query))
>>> 0, 42

子问题是从第i个数到第j个数的结果的最优min和min结果。通过计算每个子阵列上结果的最小值和最大值然后应用递归关系来确保最优性。时间复杂度为 O(n^3)，因为有 O(n^2) 个子问题，每个子问题都需要 O(n)。

编辑:

解释:

对于动态规划，确定什么是子问题以及子问题与其他子问题的关系至关重要。对于这个带有 n 数字(因此 n - 1 运算符)的问题，子问题是:通过组合中的数字和运算符可以获得的最小/最大值是多少在第 i 个数字和第 j 个数字(含)之间。

基本情况是i = j，我们只有一个数字，最小值/最大值就是它本身。

对于任何 j > i，此问题的子问题是 k 范围从 i 到 j - 1 的最小值和最大值左边部分(以 i 和 k 为两个端点的子问题)和右边部分(以 k + 1 和 为子问题j 作为两个端点)。对于每个 k，我们实际上在做的是应用第 k 运算符作为最后一个运算符，因此我们可以为每个 k 获得最小值是左边的最小值 (operator) 右边的最小值(对于最大值也是如此)。 (请注意，运算符是 * 或 +，它们是单调的，因此我们将最小值组合起来得到最小值，将最大值组合起来得到最大值。对于具有更多运算符的更通用的问题，例如作为 - 或 / 我们可能需要考虑很多情况，但基本结构应该是相同的)。所以递归关系很简单

minimum(i, j) = min(minimum(i, k) [operator] minimum(k + 1, j) for each k)

(最大值相同)

我们必须只解决每个子问题(总共 O(n^2))一次并缓存它(或者像人们说的那样记住它)并且每个子问题都需要一个 O(n) 循环求解。因此时间复杂度为 O(n^3)。

对动态规划有更深入的理解将真正帮助您解决所有类似的问题。如果您不确定在这种情况下会发生什么，我建议您阅读一些相关内容。