Leetcode 1770 Maximum Score from Performing Multiplication Operations

Problem statement

https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/

Solution

Not very difficult problem, but it is not optimized in python and get TLE withoug tricks. The idea is to use state dp(i, j, k) where we consider nums[i:j+1] and we have index k from multipliers. Notice that k is uniquiely defined by i and j. Also there will be no more than O(m^2) states.

Complexity

Time complexity is O(m^2), space complexity is the same.

Code

class Solution:
    def maximumScore(self, A, M):
        
        @lru_cache(2000)
        def dp(i, j, k):
            if k == len(M) or i > j: return 0
            return max(dp(i+1, j, k+1) + A[i]*M[k], dp(i, j-1, k+1) + A[j]*M[k])
        
        return dp(0, len(A) - 1, 0)