Minimize Result By Adding Parentheses To Expression - Leetcode Solution

The problem "Minimize Result By Adding Parentheses To Expression" on LeetCode asks to add parentheses to an arithmetic expression to minimize its result. The arithmetic expression consists of digits, '+', '-' and '*'. The problem defines the operations on the operands as follows:

• Addition: '+'
• Subtraction: '-'
• Multiplication: '*'

The problem requires you to add parentheses to the expression to minimize its result. The solution for this problem can be achieved using recursion, dynamic programming, and memoization.

Approach:

1. Recursive Approach:

The recursive approach requires a recursive function that takes the arithmetic expression as input and returns the minimum result that can be obtained after adding parentheses to the expression. The function evaluates every possible way of adding parentheses and returns the minimum of all possible results.

The function can be defined as follows:

def min_result(expr: str) -> int:
    if len(expr) == 1:
        return int(expr)
    min_val = float('inf')
    for i in range(1, len(expr), 2):
        left_expr = expr[0:i]
        op = expr[i]
        right_expr = expr[i+1:]
        left_result = min_result(left_expr)
        right_result = min_result(right_expr)
        if op == '+':
            val = left_result + right_result
        elif op == '-':
            val = left_result - right_result
        elif op == '*':
            val = left_result * right_result
        min_val = min(min_val, val)
    return min_val

The function recursively evaluates every possible way of adding parentheses and returns the minimum result that can be obtained.

2. Dynamic Programming with Memoization:

The dynamic programming approach with memoization builds upon the recursive approach by storing the results of previous computations in a memoization table. The memoization table stores the minimum result that can be obtained for a given subexpression of the arithmetic expression.

The function can be defined as follows:

def min_result_memo(expr: str, memo: dict) -> int:
    if memo.get(expr):
        return memo[expr]
    if len(expr) == 1:
        return int(expr)
    min_val = float('inf')
    for i in range(1, len(expr), 2):
        left_expr = expr[0:i]
        op = expr[i]
        right_expr = expr[i+1:]
        left_result = min_result_memo(left_expr, memo)
        right_result = min_result_memo(right_expr, memo)
        if op == '+':
            val = left_result + right_result
        elif op == '-':
            val = left_result - right_result
        elif op == '*':
            val = left_result * right_result
        min_val = min(min_val, val)
    memo[expr] = min_val
    return min_val

The memoization table keeps track of the minimum result that can be obtained for a given subexpression. The function first checks whether the memoization table has already stored the result for the subexpression. If so, it simply returns the result from the memoization table.

3. Dynamic Programming with Tabulation:

The dynamic programming with tabulation approach evaluates all possible subexpressions of the given input expression. The approach uses a 2D table to store the minimum result that can be obtained for every subexpression. The table is calculated in a bottom-up manner.

The function can be defined as follows:

def min_result_tab(expr: str) -> int:
    n = len(expr)
    dp = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dp[i][i] = int(expr[i])
    for l in range(2, n+1):
        for i in range(n - l + 1):
            j = i + l - 1
            if l == 2:
                dp[i][j] = eval(expr[i:j+1])
            else:
                min_val = float('inf')
                for k in range(i+1, j+1, 2):
                    left_result = dp[i][k-1]
                    right_result = dp[k+1][j]
                    op = expr[k]
                    if op == '+':
                        val = left_result + right_result
                    elif op == '-':
                        val = left_result - right_result
                    elif op == '*':
                        val = left_result * right_result
                    min_val = min(min_val, val)
                dp[i][j] = min_val
    return dp[0][n-1]

The outer loop iterates through the length of the subexpression, and the inner loop iterates through every possible subexpression of that length. The subexpression is defined by the outer and inner loop indices.

The if condition inside the inner loop checks if the subexpression is a binary expression (the length of the subexpression is 2). If so, the function evaluates the expression and stores it in the dynamic programming table.

Otherwise, the function evaluates the expression by recursively evaluating all possible ways of adding parentheses and storing the minimum result in the dynamic programming table. The function returns the value stored in the top right corner of the table, which represents the minimum result that can be obtained for the entire expression.

1