Problem of The Day: Maximum Score from Performing Multiplication Operations

Problem Statement

leetcode problem link

My Solution [Accepted]

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        N = len(nums)
        M = len(multipliers)
        memo = {}

        def dp(i, start, end):
            if start > end or i == M:
                return 0
            if (i,start,end) in memo:
                return memo[(i,start,end)]

            select_start = select_end = 0
            select_start = dp(i + 1, start + 1, end) + multipliers[i] * nums[start]
            select_end = dp(i + 1, start, end - 1) + multipliers[i] * nums[end]
            memo[(i,start,end)] = max(select_start, select_end)
            return memo[(i,start,end)]

        return dp(0, 0, N - 1)

Editorial

Approach 2: Top-Down Dynamic Programming

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:

        # Number of Operations
        m = len(multipliers)

        # For Right Pointer
        n = len(nums)

        memo = {}

        def dp(op, left):
            if op == m:
                return 0

            # If already computed, return
            if (op, left) in memo:
                return memo[(op, left)]

            l = nums[left] * multipliers[op] + dp(op+1, left+1)
            r = nums[(n-1)-(op-left)] * multipliers[op] + dp(op+1, left)

            memo[(op, left)] = max(l, r)

            return memo[(op, left)]

        # Zero operation done in the beginning
        return dp(0, 0)

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        # lru_cache from functools automatically memoizes the function
        @lru_cache(2000)
        def dp(i, left):
            # Base case
            if i == m:
                return 0

            mult = multipliers[i]
            right = n - 1 - (i - left)

            # Recurrence relation
            return max(mult * nums[left] + dp(i + 1, left + 1),
                       mult * nums[right] + dp(i + 1, left))

        n, m = len(nums), len(multipliers)
        return dp(0, 0)

Approach 3: Bottom-Up Dynamic Programming

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:

        # Number of Operations
        m = len(multipliers)

        # For Right Pointer
        n = len(nums)

        dp = [[0] * (m + 1) for _ in range(m + 1)]

        for op in range(m - 1, -1, -1):
            for left in range(op, -1, -1):

                dp[op][left] = max(multipliers[op] * nums[left] + dp[op + 1][left + 1],
                                   multipliers[op] * nums[n - 1 - (op - left)] + dp[op + 1][left])

        return dp[0][0]

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        n, m = len(nums), len(multipliers)
        dp = [[0] * (m + 1) for _ in range(m + 1)]

        for i in range(m - 1, -1, -1):
            for left in range(i, -1, -1):
                mult = multipliers[i]
                right = n - 1 - (i - left)
                dp[i][left] = max(mult * nums[left] + dp[i + 1][left + 1],
                                  mult * nums[right] + dp[i + 1][left])
        return dp[0][0]