Leetcode 3654. Minimum Sum After Divisible Sum Deletions

• Leetcode 3654. Minimum Sum After Divisible Sum Deletions
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3654. Minimum Sum After Divisible Sum Deletions

1. 解题思路

这一题思路上就是一个动态规划的思路，我们考虑每一个位置的情况，其如果要保留，那么我们就考虑其下一个位置的情况，如果要删除，那么就会一下子删除到其下一个与当前位置前序和对$k$同余的位置上。

因此，我们很快就能写出迭代公式，然后进行动态规划即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minArraySum(self, nums: List[int], k: int) -> int:if k == 1:return 0n = len(nums)remains = [0 for _ in range(n+1)]boundries = defaultdict(list)boundries[0].append(0)for i in range(n):remains[i+1] = (remains[i] + nums[i]) % kboundries[remains[i+1]].append(i+1)if len(boundries) == 1:return 0@lru_cache(None)def dp(idx):if idx >= n:return 0ans = math.infj = bisect.bisect_right(boundries[remains[idx]], idx)if j < len(boundries[remains[idx]]):r = boundries[remains[idx]][j]ans = min(ans, dp(r))if ans == 0:return ansif ans > nums[idx]:ans = min(ans, nums[idx] + dp(idx+1))return ansreturn dp(0)

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