确定是否可以通过重复删除给定长度且总和为给定值的连续子数组来使数组为空

Question

给定一个 array A，您可以重复删除长度等于其k总和的任何连续子数组tar。通过此过程输出是否A可以清空。

A是一个整数数组，k是一个正整数，tar是一个整数。

例如，A=[1,2,3,4];k=2;tar=5 然后您可以删除[2,3]fromA使其变为[1,4]。然后你[1,4]从A;中删除 它变得空了。因此，算法应该输出True。

目前我已经找到了一个O(n^2/k*comb(n/k,k))算法。还有更好的吗？

我的算法

首先使用dp，判断是否A[i:j]可以为空，然后枚举最后删除的子数组的所有元素，及时O(comb((j-i)/k, k))，

python3的示例代码，当k为3：

from functools import lru_cache
from itertools import accumulate

def solve(A, k, tar):
    # only works when k = 3
    assert k==3
    presum = list(accumulate(A, initial=0))

    @lru_cache(None)
    def judge(i, j):
        """ 
        find if s[i:j] can be full erased 
        """
        l,remainder = divmod(j-i,k)
        if remainder != 0 or presum[j]-presum[i] != tar*l: 
            return False
        if l<=1:
            return True

        # enumerate the last 3 elements to be erased
        
        # # find triplets that sum to tar
        for a1 in range(i, j, 3):
            for a2 in range(a1+1, j, 3):
                for a3 in range(a2+1, j, 3):
                    if A[a1]+A[a2]+A[a3]==tar:
                        prv = i
                        flag = True
                        for nxt in a1,a2,a3,j:
                            if not judge(prv, nxt):
                                flag = False
                                break
                            prv = nxt+1
                        if flag == True:
                            return True
        
        return False

    return judge(0,len(A))

print(solve([1,2,3,4,8,0],3,9))

额外的问题

k我也想知道什么时候3和是否有具体的算法2。

k=3贪婪时不起作用 的测试用例：A=[5,5,5,1,9,7,3,0,10, 5,5,5, 10,0,3,7,9,1,5,5,5];tar=15;k=3

Answer 1

对于我们处理一系列操作的问题，您通常可以通过参数化要执行的第一个或最后一个操作来获得动态编程解决方案。

对于我们的数组A = [a_0, a_1, ... a_{n-1}]，让我们猜测最后一步会是什么。它必须删除k与我们的求和的元素target，并且这些元素[x_0, x_1, ... x_{k-1}]形成 A 的子序列，该子序列将 的其他元素划分A为最多k+1其他子数组。在执行最后一个操作之前，其他子数组已经通过某些操作被完全单独删除，并且每个子数组上的子问题与我们原来的问题完全相似。这是最优子结构的一个例子。

框架已经搭建好了，我们来谈谈细节。有很多简单的边缘情况：如果k是 1，或者数组的长度不能被 整除k，或者数组的总和不正确，我们应该首先检查。我还将假设target和 的条目A都是非负的，但这可以通过对代码进行少量添加来修改，而不会影响运行时复杂性。

我们的子问题需要跟踪哪些变量？其中有当前数组的左边界和右边界，以及我们已经采用的所有外部分区元素的数量和总和。我们还不知道哪些k分区元素将出现在最后一个操作中——它们可能会分布在整个原始数组上。

我们将从左到右遍历数组，在每个点测试是否可以将当前元素用于该外部分区，或者是否将接下来的 k、2k、3k、... 元素作为一个整体进行处理。连续的子数组，然后继续。我们可以从考虑中过滤掉大多数子数组：如果子数组 S 的长度是 k 的某个倍数，m*k并且其总和是 ，则子数组 S可能是可解的m*target。我们可以使用前缀和来快速测试这一点。

Python

def solve(arr: List[int], k: int, target: int) -> bool:
    """Decide whether arr is completely removable
    Given an array of nonnegative integers arr, a positive integer length k,
    and a nonnegative target sum, decide whether we can remove all elements
    of arr by repeatedly removing k consecutive elements summing to target.
    """
    
    assert k > 0
    assert target >= 0
    
    # This section deals with any easy edge cases
    if len(arr) % k != 0:
        return False

    if k == 1:
        return all(x == target for x in arr)

    prefixes = list(itertools.accumulate(arr, initial=0))

    if target == 0:  # Assumes target >= 0 and all values >= 0
        return prefixes[-1] == 0

    if prefixes[-1] != target * (len(arr) // k):
        return False

    if k == len(arr):
        return True


    reverse_index = collections.defaultdict(list)
    starts_to_ends = collections.defaultdict(list)  # Candidate subarrays

    for right, x in enumerate(prefixes):
        remainder = x % target
        for left in reverse_index[remainder]:
            if (right - left) % k == 0:
                if (right - left) // k == (x - prefixes[left]) // target:  # Valid sum
                    starts_to_ends[left].append(right-1)

        reverse_index[remainder].append(right)

    @functools.lru_cache(None)
    def can_solve(left: int, right, outer_need: int, outer_sum_need: int) -> bool:
        elements_remaining = right - left + 1
        
        # We've reached the end of our array
        if elements_remaining == 0:
            return outer_need == outer_sum_need == 0

        # All elements must go to the outer partition
        if elements_remaining == outer_need:
            return prefixes[right + 1] - prefixes[left] == outer_sum_need
        
        # We've used k elements for the outer partition, but
        # their sum is too small
        if outer_need == 0 and outer_sum_need != 0:
            return False
        
        # Test whether we can split into two subproblems
        for poss_ending in starts_to_ends[left]:
            if poss_ending >= right:
                break
                
            if (can_solve(left, poss_ending, 0, 0)
            and can_solve(poss_ending + 1, right, outer_need, outer_sum_need)):
                return True
        
        # We are just starting a subproblem: Initialize outer partition as empty
        # and try using current element in outer partition
        if outer_need == 0 and outer_sum_need == 0:
            if (arr[left] <= target 
            and can_solve(left + 1, right, k - 1, target - arr[left])):
                return True
            
        # Try using current element in outer partition
        if outer_need > 0 and arr[left] <= outer_sum_need:
            if can_solve(left + 1, right, outer_need - 1, outer_sum_need - arr[left]):
                return True

        return False

    return can_solve(left=0, right=len(arr) - 1, outer_need=0, outer_sum_need=0)

可以修改它以实际输出要按顺序删除的数组，但需要做更多的工作。当前运行时间为O(n^2 * target * n/k)（当数组的总和或长度错误时，由于我们的预过滤技巧，节省了 k 因子）。对于许多可解数组，“贪婪”策略会起作用并且速度更快，因此可以首先尝试进行优化。

O(n^2 * target)我相信（并且有一些经验证据）通过消除递归函数内部的循环，可以将运行时间降低到。看起来您只需要测试总和有效的最大块，而不是测试下一个k、 或2k、 或元素的所有“块”作为单独的子问题，尽管我还没有找到令人满意的证明，证明这总是给出3k正确的答案。