通过添加相邻元素使所有元素相等所需的最少步骤 [英] Minimum steps needed to make all elements equal by adding adjacent elements

问题描述

我有一个大小为N的数组A，所有元素都是正整数。在一个步骤中，我可以将两个相邻的元素相加，并用它们的总和替换它们。也就是说，数组大小减少了1。现在，我需要通过执行最少的步骤来使所有元素相同。

例如：A=[1，2，3，2，1，3]。

第一步：合并索引0和1==&>A=[3，3，2，1，3]

第二步：合并索引2和3(新数组的)==>；[3，3，3，3]

因此步骤数为2。

我想不出一个直接的解决方案，所以尝试了一种递归方法，将所有索引逐个合并，并返回当数组大小为1或所有元素相等时我可以获得的最小级别。

以下是我尝试的代码：

# Checks if all the elements are same or not
def check(A):
    if len(set(A)) == 1:
        return True
    return False

# Recursive function to find min steps
def min_steps(N,A,level):
    # If all are equal return the level
    if N == 1 or check(A):
        return level
    
    # Initialize min variable
    mn = float('+inf')
    # Try merging all one by one and recur
    for i in range(N-1):
        temp = A[:]
        temp[i]+=temp[i+1]
        temp.pop(i+1)
        mn = min(mn, min_steps(N-1,temp, level+1))
    return mn

该解的复杂度为O(N^N)。我想把它减少到接近O(N^2)或O(N^3)的多项式时间。谁能帮我修改此解决方案，或者告诉我我是否遗漏了什么？

推荐答案

组合任何k个相邻的元素对(即使它们包括通过前面的组合步骤形成的元素)，总共只剩下n-k个元素，我们可以将每个元素映射回组成添加到一起形成它的元素的原始问题的连续子数组。因此，此问题等同于将数组划分为尽可能多的邻接子数组，以使所有子数组具有相同的和：可以将同一子数组中的任何相邻元素对组合为单个元素，并在子数组中重复此过程，以任何顺序选择相邻对，直到所有元素都组合为单个元素。

因此，如果有n个元素并且它们的和为T，则简单的O(NT)算法是：

1. 对于i从0到T：
   • 尝试将元素划分为每个元素都具有sum i的子数组。这相当于沿着数组扫描，如果当前子数组中的元素之和严格为<；i，则贪婪地将当前元素添加到当前子数组中。当达到总数恰好i时，当前子数组结束，新的子数组(最初具有sum 0)开始。如果添加当前元素使我们高于目标i，或者如果我们在到达目标之前用完了元素，则停止该扫描并尝试下一次外部循环迭代(值为i)。OTOH如果我们在过程中形成了k个子数组，则停止并报告n-k为组合移动的最佳(最小可能)数目。

一个小的加速将是仅尝试平均分配T的目标i值

编辑：要将时间复杂度从O(NT)提高到O(n^2)，只需尝试与数组的前缀和对应的目标i值就足够了(因为必须有一个包含第一个元素的子数组，而这个子数组只能有这样的和)。

这篇关于通过添加相邻元素使所有元素相等所需的最少步骤的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！