BinarySearch 0989 Max Multiplied Pairings Sequel

Problem statement

https://binarysearch.com/problems/Max-Multiplied-Pairings-Sequel/

Solution

Equal to Leetcode 1770 Maximum Score from Performing Multiplication Operations.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, A, M):
        @lru_cache(None)
        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)