LC 2019 [H] The Score of Students Solving Math Expression - ALawliet/algorithms GitHub Wiki

this problem is similar to the idea of Unique Binary Search Trees where you basically try all the roots to split them between a left and right side in this case to calculate the expressions

number of state * time complexity for each of dp function

m^2 (recursion) * m (sign operators) * k^2 (correct answer in range of 1000)

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        @lru_cache(None)
        def dp(i, j):
            if i == j:
                return {int(s[i])}
            
            cand = set()
            
            # try all possible sign as the last operation from i to j
            for sign in range(i+1, j, 2):
                for a in dp(i, sign-1): # left side
                    for b in dp(sign+1, j): # right side
                        res = a * b if s[sign] == '*' else a + b
                        if res <= 1000: # TLE optimization using constraint throw away too big values to reduce left/right sides to a manageable count
                            cand.add(res)
            
            return cand
        
        values = dp(0, len(s)-1)
        trueValue = eval(s)
        ans = 0
        
        for a in answers:
            if a == trueValue:
                ans += 5
            elif a in values:
                ans += 2
                
        return ans