Leetcode 3469. Find Minimum Cost to Remove Array Elements

• Leetcode 3469. Find Minimum Cost to Remove Array Elements
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3469. Find Minimum Cost to Remove Array Elements

1. 解题思路

这一题我没啥特别好的思路，就只能动态规划了，倒是也能过，不过总是有点勉强……

2. 代码实现

给出python代码实现如下：

class Solution:def minCost(self, nums: List[int]) -> int:n = len(nums)if len(set(nums)) == 1:return nums[0] * ((n+1) // 2)@lru_cache(10**4)def dp(pre, idx):if idx == n-1:return max(nums[pre], nums[idx])elif idx == n-2:candidates = sorted([nums[pre], nums[idx], nums[idx+1]])return candidates[0] + candidates[-1]return min(max(nums[idx], nums[idx+1]) + dp(pre, idx+2),max(nums[pre], nums[idx+1]) + dp(idx, idx+2),max(nums[pre], nums[idx]) + dp(idx+1, idx+2))return dp(0, 1)

提交代码评测得到：耗时6236ms，占用内存344.7MB。