思路:
1.要 iterate 一遍 multipliers, 每次取前或取后感觉可以recursive
现在可能的最大值 = max(取前+计算取剩下的最大值, 取后+计算取剩下的最大值)
2.为了加速建表记录 (s, e, i), s(start)代表取剩下的左界, e(end)代表取剩下的右界
i代表第几个operation, m代表multipliers, n代表nums
dp[s, e, i] = max(取前操作分数 m[i]*n[s] + 剩下的最大分数dp[s+1, e, i+1],
取后操作分数 m[i]*n[e] + 剩下的最大分数dp[s, e-1, i+1])
3.边界情况是 i > len(m) 代表操作完成, s > e 的情况应该不用特别判断
因为题目有说len(m) <= len(n), 能取到 s > e 你的 i 也一定会大于 len(m)
Python code:
class Solution:
def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
table = {}
def pick(s, e, i):
if (s,e,i) in table:
pass
elif i >= len(multipliers):
return 0
else:
table[s,e,i] = max(multipliers[i]*nums[s] + pick(s+1, e,
i+1), multipliers[i]*nums[e] + pick(s, e-1, i+1))
return table[s,e,i]
return pick(0, len(nums)-1, 0)
4.很可惜recursive建表还是TLE, 时间复杂度O(m^2), 应该是常数太大, 要改成iterate
建表
5.剩下的有空再补