HardNo. 1770
Maximum Score from Performing Multiplication Operations — LeetCode 1770 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given two 0-indexed integer arrays nums and multipliers of size n and m respectively, where n >= m. You begin with a score of 0.
Example
- Input
- nums = [1,2,3], multipliers = [3,2,1]
- Output
- 14
- Explanation
- An optimal solution is as follows:
Python solution
class Solution:
def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
@cache
def f(i, j, k):
if k >= m or i >= n or j < 0:
return 0
a = f(i + 1, j, k + 1) + nums[i] * multipliers[k]
b = f(i, j - 1, k + 1) + nums[j] * multipliers[k]
return max(a, b)
n = len(nums)
m = len(multipliers)
return f(0, n - 1, 0)Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1770. Maximum Score from Performing Multiplication Operations is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1774 | Closest Dessert Cost | Medium |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
| 0063 | Unique Paths II | Medium |
| 0064 | Minimum Path Sum | Medium |
Frequently asked questions
- How hard is LeetCode 1770. Maximum Score from Performing Multiplication Operations?
LeetCode 1770. Maximum Score from Performing Multiplication Operations is rated Hard on LeetCode.
- What topics does LeetCode 1770. Maximum Score from Performing Multiplication Operations cover?
LeetCode 1770. Maximum Score from Performing Multiplication Operations is tagged Array and Dynamic Programming on LeetCode.