思路:
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.剩下的有空再補