通过添加相邻元素使所有元素相等所需的最少步骤

Question

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

例如：A = [1,2,3,2,1,3].

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

第 2 步：合并索引 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) 的多项式时间。谁能帮我修改这个解决方案或告诉我是否遗漏了什么？

Answer 1

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

因此，如果有 n 个元素并且它们的总和为 T，那么一个简单的 O(nT) 算法是：

对于从 0 到 T 的 i：
- 尝试将元素划分为子数组，每个子数组的总和为 i。这相当于沿数组扫描，如果元素总和为 i，则贪婪地将当前元素添加到当前子数组当前子数组严格 < i。当总数刚好达到 i 时，当前子数组结束，新的子数组（初始总和为 0）开始。如果添加当前元素使我们超出了 i 的目标，或者如果我们在到达目标之前运行超出了元素，则停止此扫描并尝试下一个外循环迭代（i 的值）。 OTOH 如果我们走到最后，在这个过程中形成了 k 个子阵列，停止并报告 n-k 作为最佳（最小可能）组合移动数。

一个小的加速将是只尝试平均除以 T 的目标 i 值。

编辑： 为了将时间复杂度从 O(nT) 提高到 O(n^2)，只需尝试对应于数组（因为必须有一个包含第一个元素的子数组，而这个子数组只能有这样的和）。

通过添加相邻元素使所有元素相等所需的最少步骤

Minimum steps needed to make all elements equal by adding adjacent elements

arrays

recursion

dynamic-programming

backtracking

python-3.x