求将数组所有元素减至0的最少操作次数的算法问题求助

问题描述 #

给定一个正整数数组，可选择任意连续区间，将区间内所有数减去同一个值（操作后元素不能为负），求最少需要多少次该操作可使数组所有元素变为0。

我的尝试与问题 #

我尝试使用贪心算法：每次选择当前区间内的最小值，将区间内所有数减去该值，递归处理分割后的子区间，直到所有元素为0。以下是C++实现代码：

#include <iostream>
#include <vector>

using namespace std;

int foo(std::vector<int> &v, int l, int r) {
    int min = 0x3f3f3f3f;
    vector<int> idx;
    for (int i = l; i <= r; i++) {
        min = std::min(min, v[i]);
    }
    for (int i = l; i <= r; i++) {
        v[i] -= min;
        if (v[i] == 0) {
            idx.push_back(i);
        }
    }
    cout << "l: " << l << "r: " << r << " delete: " << min << endl;
    if (idx.size() == r - l + 1) {
        return 1;
    }
    int res = 1;
    int tmp_l = l;
    for (int x : idx) {
        if (tmp_l < x) {
            res += foo(v, tmp_l, x - 1);
        }
        tmp_l = x + 1;
    }
    if (tmp_l <= r) {
        res += foo(v, tmp_l, r);
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> v;
    int tmp;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        v.push_back(tmp);
    }
    cout << foo(v, 0, v.size() - 1);
}

该解法在测试用例：

5
3 3 2 3 3

中可以得到正确结果，但在测试用例：

10
2 3 4 5 1 2 3 1 2 3

中得到结果9，我误以为正确答案是8（认为最优第一步是选择减去2而非区间最小值1），但实际该测试用例的正确最少操作次数应为9次。

正确思路与提示 #

核心思路 #

这个问题等价于**“从全0数组通过最少次数的连续区间加法操作得到目标数组”的逆问题，两者的最少操作次数完全相同。其核心解法基于差分思想**：

1. 初始化操作次数为数组的第一个元素值。
2. 遍历数组从第二个元素开始，若当前元素大于前一个元素，将两者的差值加到操作次数中。
3. 最终的总和即为最少操作次数。

原理说明 #

每次对连续区间[l, r]减去值val，等价于在差分数组中对d[l] -= val、d[r+1] += val（若r+1 < n）。要让原数组全为0，需要抵消差分数组中所有的正数值——每个正差值代表需要额外的操作来覆盖“上升”的部分，而连续的上升段可以通过一次操作完成。

代码实现示例 #

#include <iostream>
#include <vector>

using namespace std;

int minOperations(vector<int>& nums) {
    if (nums.empty()) return 0;
    int res = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > nums[i-1]) {
            res += nums[i] - nums[i-1];
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    cout << minOperations(v) << endl;
    return 0;
}

对测试用例的验证 #

对于测试用例[2,3,4,5,1,2,3,1,2,3]：

• 初始值：res = 2
• 依次计算正差值：3-2=1、4-3=1、5-4=1、2-1=1、3-2=1、2-1=1、3-2=1
• 总和：2+1+1+1+1+1+1+1=9，与贪心算法的结果一致，这说明该测试用例的正确最少操作次数确实为9次。

内容的提问来源于stack exchange，提问作者yixing