仅当乘积小于等于 k ​​时，通过将相邻元素相乘来最小化数组元素

Question

我最近在一次在线评估中遇到了这个问题。

arr = [2,6,2,4] 
k = 15

仅当两个相邻元素的乘积小于 时，才需要通过相乘来最小化数组元素k。

例子：

(2,6,2,4)
(2*6,2*4) --> since 12 and 8 are less than k which is 15
(12,8)

还可以遵循以下模式：

(2,6,2,4)
(2,6*2,4) 
(2,12,4) --> no . of  elements is 3 which is more than 2 thus non-optimal.

我已经被这个问题困扰好几天了。

我尝试解决矩阵链乘法问题，但无法取得任何进展。主要区别在于，在 MCM 问题中，所有矩阵都可以相互相乘。不存在两个矩阵不能相乘的情况。

有什么提示吗？

Answer 1

由于数组的值严格为正数，因此您可以使用贪心算法：继续将值相乘，直到下一次相乘等于k或更多。发生这种情况时，启动一个新块并将乘积重置为当前数组值。通过这种方式，我们将块边界尽可能地放在右侧。我们可以看到，如果我们将一个块边界向左移动更多，这永远不会减少所需块的数量。

下面是这个贪婪算法在（简单）JavaScript 中的实现：

function solve(arr, k) {
    if (arr.length == 0) return 0; // Boundary case
    
    let product = 1;
    let count = 1;
    
    for (let i = 0; i < arr.length; i++) {
        product = product * arr[i];
        if (product >= k) { // Start a new chunk
            product = arr[i];
            count++;
        }
    }
    return count;
}

// Example run
const arr = [2,6,2,4]; 
const k = 15;
const result = solve(arr, k);
console.log("Number of chunks", result);

如果我们允许 0 作为可能的数组值，并且k严格为正数，那么零的出现将导致结果 1：所有值都可以乘以一个乘积，即 0。

如果允许负数组值，则该算法将不再正常工作。