Dynamic programming spoj proof LISA

Question

I was trying to solve https://www.spoj.com/problems/LISA/

In the problem, the expression is given which has only * and +. Placing bracket maximum value need to output.

like

 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

The implementation of 2D dynamic problem way of solving I came across is like below. Taking each number is matrix row and column and doing bottom to top approach.

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

I am not able to prove that the result I am getting is maximum and correct. How to prove below solution is max and optimal?

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

This problem can be categorized as divide and conquer problem with memoization.

Imagine your string is s = s1 op1 s2 op2 s3 op3 s4

Now you can partition s at each op

Lets say you partition s at op1 to give you two strings :

Left string : s1 and

Right string : s2 op2 s3 op3 s4.

Lets say the minimum, maximum value that can be obtained for left string are min1, max1

and for right string are : min2, max2.

You might think that min1 op1 min2 is minimum and max1 op1 max2 is maximum

But not yet done.

You need to do it for each op and accumulate values for min and max. Why? Because the partition at op1 might not be optimal.

Then out of all those partitions, pick the min(mins) and max(maxs)

You could recursively implement this with remembering the results in Java like:

private static int[] recurse( String input, Map<String, int[]> map ) {
    if ( map.containsKey(input) ) {
        return map.get(input);
    }

    int[] ans = null;
    List<Integer> mins = new ArrayList<>();
    List<Integer> maxs = new ArrayList<>();
    for ( int i = 0; i < input.length(); i++ ) {
        if ( !Character.isDigit( input.charAt(i) ) ) {
            String left = input.substring(0, i);
            String right = input.substring(i+1);

            int[] leftResult = recurse(left, map);
            int[] rightResult = recurse(right, map);

            int leftMin = leftResult[0];
            int leftMax = leftResult[1];

            int rightMin = rightResult[0];
            int rightMax = rightResult[1];

            switch( input.charAt(i) ) 
            {
            case '+':
                mins.add( leftMin + rightMin );
                maxs.add( leftMax + rightMax );
                break;
            case '*':
                mins.add( leftMin*rightMin );
                maxs.add( leftMax*rightMax );
                break;
            default:
                    break;
            }
        }
    }

    if ( mins.isEmpty() || maxs.isEmpty() ) {
        ans = new int[]{Integer.valueOf(input), Integer.valueOf(input)};
    } else {
        ans[0] = Integer.MAX_VALUE;
        ans[1] = Integer.MIN_VALUE;
        for ( int i = 0; i < mins.size(); i++ ) {
            ans[0] = Math.min( ans[0], mins.get(i) );
            ans[1] = Math.max( ans[1], maxs.get(i) );
        }
    }

    map.put( input, ans );
    return ans;
}

private static void getMinMax( String in ) {
    if ( in.isEmpty() ) {
        System.out.println("0 0");
        return;
    }
    int[] ans = recurse(in, new HashMap<String, int[]>() );
    System.out.println(ans[1] + " " + ans[0]);

}

Answer 2

This is my implementation: (it assumes the query is well-formed)

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

The subproblem is the optimal min and min result of the result from the i-th number to the j-th number. The optimality is assured by calculating the min and max of the results on every subarray then apply the recurrence relation. The time complexity is O(n^3) since there are O(n^2) subproblems and each takes O(n).

Edit:

Explanation:

For dynamic programming, it's crucial to identify what is the subproblem and how a subproblem relates to other subproblems. For this problem with say n numbers (hence n - 1 operators), the subproblem is: what is the min/max value you can get by combining the numbers and operators in between the i-th number and the j-th number (inclusive).

The base case is i = j, we have only one number, the min/max is itself.

For any j > i, the subproblems to this problem is for k ranging from i to j - 1 the minimum and maximum value of the left part (subproblem with i and k as the two endpoints) and the right part (subproblem with k + 1 and j as the two endpoints). For each k what we are essentially doing is applying the k-th operator as the last operator, hence the minimum we can get for each k is the minimum of left (operator) minimum of right (similarly for maximum). (Note that the operators are either * or +, which are monotonic so we combine minimums to get minimum and maximums to get maximum. For a more generic problem with more operators such as - or / we probably need to consider a lot of cases but the basic structure should be the same). So the recurrence relations is simply

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

(same for max)

We have to solve each subproblem (total O(n^2) of them) for once only and cache it (or memoize it as people would say) and each subproblem requires an O(n) loop to solve. Hence the time complexity is O(n^3).

A deeper understanding of dynamic programming would really help you solve all similar problems. I suggest read something about it if you are not sure what to expect in such a setting.