最近遇到一个算法问题，如下：
给定一个正整数数组，你可以选择数组中的任意连续区间，并将该区间内的每个数字减去相同的值，询问至少需要执行多少次上述操作才能使数组中的所有数字都为 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。最佳过程是
origin:
2 3 4 5 1 2 3 1 2 3
1 - 0 1 2 3 1 2 3 1 2 3
2 - 0 0 1 2 0 1 2 0 1 2
3 - 0 0 0 1 0 1 2 0 1 2
4 - 0 0 0 0 0 1 2 0 1 2
5 - 0 0 0 0 0 0 1 0 1 2
6 - 0 0 0 0 0 0 0 0 1 2
7 - 0 0 0 0 0 0 0 0 0 1
8 - 0 0 0 0 0 0 0 0 0 0
看来每次都找到最小的数字并不是最好的策略，在这个测试用例中，首先选择数字2，而区间内的最小数字是1。
这不是一个算法，但我确实有一个证据，证明它是 NP 完全的，通过子集和的减少来实现。
让S = [s1, s2, ..., sn]是一个正整数数组n，并且k是另一个正整数。考虑以下数字。
[s1, s1+s2, s1+s2+s3, ..., s1+s2+...+sn, k]
n当且仅当k是 中数字的某个子集之和时，这才可以分步求解S。
我实际上知道一种通过A* search解决这个问题的方法。但存在组合爆炸。这是这个想法的概要。
给定最佳答案，我们可以重新排列项的顺序，以便我们始终从第一个非零项中减去。启发式是m列表中的值在某些地方发生了变化。我们只能m通过一次减法最多减少 2（我们可以潜在地消除两条边）。所以 的上限m/2就是剩下的最少步数。
我被要求提供减少的证据。
k“如果是子集的总和，则可以完成S”部分很简单。移除的方块的高度为s1, s2, ..., sn。第i一个块从索引i-1到任一索引n-1，或者n取决于是否i是子集和中的一项。
“仅当”更为复杂。
首先，为了使索引变得容易，让我们S用数组替换。所以我们不说，而是s1说S[0]。（请注意，会有很多一一索引问题。）因此，我们的示例数组n+1元素是
a = [a[0], a[1], ..., a[n]]
= [S[0], S[0] + S[1], S[0] + S[1] + S[2], ..., S[0] + ... + S[n-1], k]
现在假设我们可以用块将整个数组清零n。利用加法是可交换的事实，让我们按删除的第一个索引重新排列块。这保证了我们将数组中从左到右的数字清零。让我们将其设为从第一个块被取出后taken[i][j]取出的金额。a[j]i
请注意，它taken[0][j]始终为零，因为我们尚未减去任何内容。
假设在块a[j]之后尚未清零i。到目前为止，每个块都必须在 或之前开始j，并且可能只有一些继续j+1，所以taken[i][j] >= taken[i][j+1]。因为a[0] < a[1] < .. < a[n-1]，这意味着我们只能将每个块最多归零一个。n由于我们设法将所有带有块的索引清零n，因此我们必须将每个块的其中一个索引清零。（并且，在某些时候，我们将设法将 归零a[n]，即k。）
现在我们的目标是看到taken[i][j]必须始终是 的子集之和[S[0], S[1], ..., S[i-1]]。这意味着就是taken[n][n]这样。由于它被归零k，这意味着它k是一个子集的总和S。
我们将通过展示更强大的东西来做到这一点。
如果i <= j < l则taken[i][j]是 的子集之和[S[0], S[1], ..., S[i-1]]，并且taken[i][l]是 的子集之和。
首先，小案子。taken[0][j]总是0因为当我们拿走了 0 个街区时，我们并没有拿走任何东西。0当然，是空集的子集之和。空集是空集的子集。
我们会i=1用手做。我们需要归零a[0] = S[0]。因此，第一个块具有高度S[0]和一定的长度，这意味着它taken[1][j]必须是S[0]或0取决于您是否超出块的末端。一旦它转动，0它就会保持不变0，所以如果j < k那么taken[1][l]是 的子集之和taken[1][j]。
现在介绍一般归纳案例。第i块需要完成清零a[i-1] = S[0] + S[1] + ... + S[i-1]。我们已经去掉了taken[i-1][i-1]的子集之和[S[0], S[1], ..., S[i-2]]。因此，i第 个块是 中该集合的补码之和[[S[0], S[1], ..., S[i-1]]。
如果i <= j，则taken[i-1][j]是 的子集之和taken[i-1][i-1]。因此，第 块S中的元素尚未在 中。因此，无论第th 个块是否包含在 中，您都会得到 的子集之和。itaken[i-1][j]itaken[i][j][S[0], S[1], ..., S[i-1]]
现在假设j < l. 我们已经得到了taken[i-1][l]组成 的项子集的总和taken[i-1][j]。第ith 块可能包含也可能不包含在taken[i][j]和中taken[i][l]。但如果它包含在中，taken[i][l]那么它必须包含在 中taken[i][j]。这导致了三种情况，在所有情况下taken[i][l]都是属于 的部分的项子集的总和taken[i][j]。
所以通过归纳我们就得到了结果。正如已经指出的，这意味着k = taken[n][n]是 的子集之和[S[0], S[1], ..., S[n-1]]。因此解决数组的这个问题a就可以解决子集和问题。