Leetcode # 1770. Maximum Score from Performing Multiplication Operations

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

Solution: Top-Down DP

m := len(multipliers)
n := len(nums)

(end – start) = n – 1, n -2, …, n – m
當 (end – start) == n – m ，start = 0, 1, …, m – 1
所以 time/space complexity 為 O(m ** 2)

Time Complexity: O(m ** 2)
Space Complexity: O(m ** 2)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
    dp = {}
    def max_score(start, end):
      if (start, end) not in dp:
        if end - start == len(nums) - len(multipliers):
          dp[(start, end)] = max(multipliers[-1] * nums[start], 
                                 multipliers[-1] * nums[end])
        else:
          i = len(nums) - (end - start + 1)
          dp[(start, end)] = max(
            multipliers[i] * nums[start] + max_score(start + 1, end), 
            multipliers[i] * nums[end]   + max_score(start, end - 1))
      return dp[(start, end)]
    return max_score(0, len(nums) - 1)

Solution: Bottom-Up, Optimized Space Complexity

Top-Down to Bottom-Up

Steps

1. Start with a completed top-down implementation.

參考 Solution: Top-Down DP

2. Set base cases.

Base Case: 

dp[(start, end)] = max(
    multipliers[-1] * nums[start],
    multipliers[-1] * nums[end])

3. Write a for-loop(s) that iterate over your state variables.

注意點：

1. If you have multiple state variables,
   you will need nested for-loops.
2. These loops should start iterating from the base cases.

—

State Transition Equation: 

dp[(start, end)] = max(
    multipliers[i] * nums[start] + max_score(start + 1, end),
    multipliers[i] * nums[end]   + max_score(start, end - 1))

將遞迴函式max_score()替換成dp：

dp[(start, end)] = max(
    multipliers[i] * nums[start] + dp[(start + 1, end)],
    multipliers[i] * nums[end]   + dp[(start, end - 1)])

又 base case: 

dp[(start, end)] = max(
    multipliers[-1] * nums[start],
    multipliers[-1] * nums[end])

≡

dp[(start, end)] = max(
    multipliers[-1] * nums[start] + 0,
    multipliers[-1] * nums[end]   + 0)

我們可以把dp[m - 1]就可以併入dp[i] for i in range(m - 1, -1, -1)
base case 變為dp[m] = [0 for start in range(m + 1)]

—

在同一階段的 states（dp[i][(start, end)]）
i = len(nums) - (end - start + 1) ⇒ end – start == n – i – 1
即其end - start的值皆是相同的
只需要start一個變數就能算出end

dp[(start, end)] → dp[start, start + n - i - 1]

i = len(nums) - (end - start + 1)
而 (end – start + 1) = n, n – 1, …, n – m + 1 ，則 i = 0, 1, …, m – 1

Result

Time Complexity: O(m ** 2)
Space Complexity: O(m ** 2)O(m) (dp 最大長度為 m + 1)
(The input and output generally do not count towards the space complexity.)

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

Last Updated on 2023/08/16 by A1go