Skip to main content

1770. Maximum Score from Performing Multiplication Operations

Python​

Top Down DP​

  • 直接@cache會memory limit exceed
  • maxsize=2048是try & error試出來的，這題做Bottom Up會理想一點
from functools import lru_cache


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

        @lru_cache(maxsize=2048)
        def dp(left: int, right: int):
            if right == m:
                return 0

            take_left = nums[left] * multipliers[right] + dp(left+1, right+1)
            take_right = nums[n-(right-left)-1] * multipliers[right] + dp(left, right+1)

            return max(take_left, take_right)

        return dp(0, 0)

Bottom Up DP​

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 step in range(m-1, -1, -1):
            for left in range(step, -1, -1):
                dp[step][left] = max(
                    multipliers[step]*nums[left] + dp[step+1][left+1],
                    multipliers[step]*nums[n-(step-left)-1] + dp[step+1][left]
                )

        return dp[0][0]