Recently I came across an algorithmic problem which is described below:

最近我遇到了一个算法问题，描述如下：

Given an array of positive integers, you can pick any consecutive interval within the array and subtract every number within that interval by the same value, ask how many times at least the above operation is needed to make all the numbers in the array 0.

I'm trying to use greedy algorithm but I'm running into local minima problem, so I realized that I have to use dynamic programming but I can't find the recursion formula, am I thinking correctly? If not what is the correct way of thinking? Can anyone give me a hint about this problem?

我试图使用贪婪算法，但我遇到了局部极小值问题，所以我意识到我必须使用动态编程，但我找不到递归公式，我的想法正确吗？如果不是，正确的思维方式是什么？关于这个问题，有人能给我一点提示吗？

I have seriously thought about this problem but I just can't come up with a result and it's frustrating me

我认真地考虑了这个问题，但就是想不出一个结果，这让我很沮丧

EDIT:

编辑：

here is my solution: using greedy algorithm, every time choose to the lowest number in the interval, subtract every number within the interval by this number, do this recursivly until all numbers are zero.The C++ implementation is as follows:

这是我的解决方案：使用贪婪算法，每次选择区间中最小的数字，用这个数字减去区间内的每个数字，递归地进行，直到所有的数字都为零。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);
}

testcase formation is as follow.(first line describe the size of array, second line describe numbers in the array)

测试用例格式如下(第一行描述数组的大小，第二行描述数组中的数字)

5
3 3 2 3 3

my solution meets local minium in the following testcase:

我的解决方案在以下测试用例中遇到了本地最小化：

10
2 3 4 5 1 2 3 1 2 3

my solution gives answer 9 but the correct answer is 8.
the optimial process is

我的解决方案给出了答案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

it seems that finding the lowerest number every time is not the best stragery, in this test case, number 2 is selected at first whereas the minium number in the interval is 1.

似乎每次都找到最小的数字并不是最好的策略，在这个测试用例中，首先选择数字2，而区间中的最小数字是1。

This isn't an algorithm, but I do have a proof that it is NP-complete by a reduction from subset sum.

这不是一种算法，但我确实有一个证明，证明它是NP-完全的，通过从子集和中减去。

Let S = [s1, s2, ..., sn] be an array of n positive integers, and k be another positive integer. Consider the following numbers.

设S=[s1，s2，…，sn]是n个正整数的数组，k是另一个正整数。请考虑以下数字。

[s1, s1+s2, s1+s2+s3, ..., s1+s2+...+sn, k]

This is solvable in n steps if and only if k is the sum of some subset of the numbers from S.

这是n步可解的当且仅当k是来自S的数的某个子集的和。

I actually do know a way to solve this with A* search. But there is a combinatorial explosion. Here is an outline of the idea.

我确实知道用A*Search解决这个问题的方法。但现在出现了一场组合爆炸。以下是这一想法的概要。

Given an optimal answer, we can rearrange the order of the terms so that we're always subtracting from the first non-zero term. And the heuristic is that there is some number m of places where the value in the list changes. We can only reduce m by at most 2 with a single subtraction (we can eliminate both edges potentially). So the ceiling of m/2 is the least number of steps left.

给出一个最佳答案，我们可以重新安排项的顺序，这样我们总是从第一个非零项中减去。启发式方法是，列表中的值有一定数量的m个位置改变。我们最多只能用一次减法将m减去2(我们可以潜在地消除两条边)。所以m/2的上限是剩下的最少步数。

I was asked for evidence of the reduction.

我被要求提供减少的证据。

The "can be done if k is a sum of a subset of S" part is simple. The blocks removed are of heights s1, s2, ..., sn. The ith block goes from index i-1 to either index n-1 or n depending on whether i is one of the terms in the subset sum.

“如果k是S的一个子集的和就可以做”这一部分很简单。移走的积木高度为s1、s2、...、sn。根据i是否是子集SUM中的项之一，第i块从索引i-1行进到索引n-1或n。

The "only if" is more complicated.

“只有如果”这一点更为复杂。

First, to make indexing easy, let's replace S with an array. So instead of saying s1 we'll say S[0]. (Note, there will be lots of off by one indexing issues.) And therefore our example array with n+1 elements is

首先，为了简化索引，让我们用数组代替S。所以我们不写s1，而是写S[0]。(Note，将有很多关闭由一个索引的问题。）因此，我们的示例数组有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]

Now suppose we can zero out the whole array with n blocks. Using the fact that addition is commutative, let's rearrange the blocks by the first index removed. This guarantees that we zero out the numbers in the array from left to right. Let's let taken[i][j] be the amount taken from a[j] after the first i blocks are taken.

现在假设我们可以用n个块将整个数组置零。利用加法是可交换的这一事实，让我们根据删除的第一个索引重新排列块。这保证了我们从左到右将数组中的数字置零。假设Take[i][j]是在第一个i块被获取之后从a[j]中获取的量。

Note that taken[0][j] is always zero, because we have not yet subtracted out anything.

注意Take[0][j]总是零，因为我们还没有减去任何东西。

Suppose that a[j] is not yet zeroed out after i blocks. Every block so far must start at or before j, and possibly only some continue to j+1, so taken[i][j] >= taken[i][j+1]. Since a[0] < a[1] < .. < a[n-1], this means we can only zero out at most one per block. Since we manage to zero out all n of those with n blocks, we must zero out one of those indexes per block. (And, at some point, we'll manage to zero out a[n], which is k.)

假设在i个块之后a[j]还没有被置零。到目前为止，每个块都必须从j开始或在j之前，可能只有一些块继续到j+1，所以取[i][j]>=取[i][j+1]。由于a[0]

Now our goal is to see that taken[i][j] must always be the sum of a subset of [S[0], S[1], ..., S[i-1]]. This will mean that taken[n][n] is. And since that zeroed out k, that means that k is the sum of a subset of S.

现在我们的目标是，Take[i][j]一定总是[S[0]，S[1]，…，S[i-1]]的子集的和。这将意味着Take[n][n]是。由于k被归零，这意味着k是S的一个子集的和。

We will do this by showing something stronger.

我们将通过展示一些更强大的东西来做到这一点。

If i <= j < l then taken[i][j] is the sum of a subset of [S[0], S[1], ..., S[i-1]], and taken[i][l] is the sum of a subset of that.

如果i<=j

First, the trivial case. taken[0][j] is always 0 because when we have taken 0 blocks away, we haven't taken anything away. 0 is, of course, the sum of a subset of the empty set. And the empty set is a subset of the empty set.

首先，是一个微不足道的案例。Take[0][j]总是0，因为当我们离开0个街区时，我们没有拿走任何东西。当然，0是空集的子集的和。并且空集是空集的子集。

We'll do i=1 by hand. We need to zero out a[0] = S[0]. Therefore the first block has height S[0] and some length, meaning that taken[1][j] has to be either S[0] or 0 depending on whether you're off the end of the block. And once it turns 0 it stays 0, so if j < k then taken[1][l] is the sum of a subset of taken[1][j].

我们将手工计算i=1。我们需要将a[0]=S[0]置零。因此，第一个块具有高度S[0]和一定的长度，这意味着所取的[1][j]必须是S[0]或0，这取决于您是否离开了块的末尾。而一旦它变成0，它就保持0，所以如果j

And now for the general induction case. The ith block needs to finish zeroing out a[i-1] = S[0] + S[1] + ... + S[i-1]. We have already taken away taken[i-1][i-1] which is a sum of a subset of [S[0], S[1], ..., S[i-2]]. And therefore the ith block is the sum of the complement of that set in [[S[0], S[1], ..., S[i-1]].

现在是一般的入职案例。第i个块需要将a[i-1]=S[0]+S[1]+…+S[i-1]清零。我们已经去掉了[i-1][i-1]，它是[S[0]，S[1]，…，S[i-2]]的一个子集的和。因此，第i个块是[[S[0]，S[1]，…，S[i-1]]中那个块的补集的和。

If i <= j, then taken[i-1][j] is the sum of a subset of taken[i-1][i-1]. Therefore the elements of S in the ith block are NOT already in taken[i-1][j]. Therefore whether or not the ith block is included in taken[i][j], you get the sum of a subset of [S[0], S[1], ..., S[i-1]].

如果i<=j，则Take[i-1][j]是Take[i-1][i-1]的子集的和。因此，第i块中的S元素还没有被采用[i-1][j]。因此，无论第i个块是否包含在Take[i][j]中，都会得到[S[0]，S[1]，…，S[i-1]]的子集的和。

Now suppose that j < l. We already had taken[i-1][l] is the sum of a subset of the terms that made up taken[i-1][j]. The ith block may or may not be included in taken[i][j] and taken[i][l]. But if it is included in taken[i][l] then it MUST be included in taken[i][j]. This leads to three cases, in all of which taken[i][l] is a sum of the subset of the terms that are part of taken[i][j].

现在假设j

So by induction we have the result. And as already noted, that means that k = taken[n][n] is the sum of a subset of [S[0], S[1], ..., S[n-1]]. So solving this problem for the array a leads to a solution of the subset sum problem.

所以通过归纳法，我们得到了结果。如前所述，这意味着k=Take[n][n]是[S[0]，S[1]，…，S[n-1]]的子集的和。因此，解决阵列A的这个问题将导致子集和问题的解。

If the array is only of modest size you can do it by a recursive search ... but the time complexity isn't great.

如果数组只有中等大小，您可以通过递归搜索来完成...但时间复杂性并不是很大。

EDIT: code improved by:

编辑：代码经过以下改进：

• not spawning a recursion where improvement is impossible (there is a smaller positive value to left or right, or an equal value to the left);


• splitting up the subsequences into positive subsequences surrounded by 0s.

Can now get to about N=30 with reasonable running time.

在合理的运行时间下，现在可以达到N=30左右。

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;

//======================================================================

template<typename T> ostream & operator << ( ostream & out, const vector<T> &V )
{
   for ( auto e : V ) out << e << ' ';
   return out;
}

//======================================================================

int best( const vector<int> &V )
{
   int b = V.size();
   if ( b == 0 || *max_element( V.begin(), V.end() ) == 0 ) return 0;
   if ( b == 1 )                                            return 1;

   for ( int i = 0; i < V.size(); i++ )
   {
      // Reduce values around position i and put in a temporary vector
      int val = V[i];
      if ( i     > 0        && V[i-1] > 0 && V[i-1] <= val ) continue;    // no improvement possible
      if ( i + 1 < V.size() && V[i+1] > 0 && V[i+1] <  val ) continue;    // no improvement possible
      vector<int> temp = V;
      int imin = i, imax = i;
      if ( val > 0 )
      {
         imin = i;   while( imin     > 0        && V[imin-1] >= val ) imin--;
         imax = i;   while( imax + 1 < V.size() && V[imax+1] >= val ) imax++;
         for ( int j = imin; j <= imax; j++ ) temp[j] -= val;
      }

      int btest = ( val > 0 );
      int j1, j2;
      // Deal with left side of modified array in positive subarrays [j1,j2] surrounded by 0
      j2 = i - 1;   while ( j2 >= 0 && temp[j2] == 0 ) j2--;
      while( j2 >= 0 )
      {
         j1 = j2;   while( j1 - 1 >= 0 && temp[j1-1] != 0 ) j1--;
         vector<int> left( temp.begin() + j1, temp.begin() + j2 + 1 );
         btest += best( left );
         if ( btest >= b ) break;
         j2 = j1 - 1;   while ( j2 >= 0 && temp[j2] == 0 ) j2--;
      }
      if ( btest >= b ) continue;

      // Deal with right side of modified array in subarrays [j1,j2] surrounded by 0
      j1 = i + 1;   while ( j1 < temp.size() && temp[j1] == 0 ) j1++;
      while( j1 < temp.size() )
      {
         j2 = j1;   while( j2 + 1 < V.size() && temp[j2+1] != 0 ) j2++;
         vector<int> right( temp.begin() + j1, temp.begin() + j2 + 1 );
         btest += best( right );
         if ( btest >= b ) break;
         j1 = j2 + 1;   while ( j1 < V.size() && temp[j1] == 0 ) j1++;
      }
      if ( btest < b ) b = btest;
   }
   return b;
}

//======================================================================

int main()
{
   vector<vector<int>> tests = { { 3, 4, 1, 2 },
                                 { 3, 4, 1 },
                                 { 3, 3, 2, 3, 3 },
                                 { 2, 5, 10, 7 },
                                 { 2, 5, 0, 2, 5 },
                                 { 4, 9, 11, 6, 3, 1, 4 },
                                 { 2, 3, 4, 5, 1, 2, 3, 1, 2, 3 } };

   for ( const auto &v : tests ) cout << v << "----> " << best( v ) << '\n';

   const int N = 30;
   vector<int> v( N );
   srand( time( 0 ) );
   for ( int &e : v ) e = 1 + rand() % 100;
   cout << "\nRandom vector of size " << N << ":\n";
   cout << v << " ----> " << best( v ) << '\n';
}

Output:

产出：

3 4 1 2 ----> 3
3 4 1 ----> 2
3 3 2 3 3 ----> 3
2 5 10 7 ----> 3
2 5 0 2 5 ----> 4
4 9 11 6 3 1 4 ----> 5
2 3 4 5 1 2 3 1 2 3 ----> 8

Random vector of size 30:
16 39 88 24 80 77 76 57 64 7 30 31 14 1 7 95 95 54 53 83 99 90 37 6 61 96 25 36 56 22  ----> 24

Consider each element as either rightmost of a disjoint section or in the middle or leftmost position of a disjoint section (by "disjoint," I mean a section where the reductions in it do not extend further). If it is rightmost of a disjoint section, it makes no sense to reduce the element more than once. Why? There are two cases: (1) we're reducing an equal length section twice (or more), which clearly makes no sense since we could reduce it once by the full amount for a lower cost; or (2) we're reducing a longer section first, then a shorter one (or more; we can reorder the reductions for similar effect). But the latter operation could be split into a separate move for each of those sections for the same cost.

将每个元素视为不相交部分的最右侧或不相交部分的中间或最左侧位置(这里的“不相交”指的是其中的减数不会进一步扩展的部分)。如果它是不相交截面的最右侧，则多次减少该元素是没有意义的。为什么？有两种情况：(1)我们将等长的部分减少两次(或更多)，这显然没有意义，因为我们可以将其减少一次，以获得更低的成本；或(2)我们首先减少较长的部分，然后减少较短的部分(或更多；我们可以为类似的效果重新排序减少)。但后一项行动可以拆分为每一部分的单独搬家，成本相同。

11111111
    2222

would have the same cost as

会有相同的成本

11113333

If the element is not at the end of a disjoint section, it necessarily is first reduced by some ordered effect of the end elements that were fully removed, and the residual, if any.

如果元素不在不相交部分的末端，则必须首先通过被完全移除的末端元素和剩余元素(如果有的话)的某种有序效应来减少它。

JavasScript code:

Java脚本代码：

// Returns sums from cs that do not
// exceed n.
function getCombs(cs, n, i = 0) {
  if (i == cs.length) {
    return [];
  }
  
  const result = [];
  
  for (const [s, ks] of getCombs(cs, n, i + 1)) {
    result.push([s, ks]);
    if (s + cs[i] <= n) {
      result.push([
        s + cs[i],
        [cs[i]].concat(ks)]);
    }
  }
  
  if (cs[i] <= n) {
    result.push([cs[i], [cs[i]]]);
  }
  
  return result;
}

function f(A) {
  const dp = {};
  
  function g(i, cs) {
    const key = String([i, cs]);
    if (key in dp) {
      return dp[key];
    }
    
    const combs = getCombs(cs, A[i]);
    
    // Base case last/first element
    if (i == 0) {
      if (A[i] == 0) {
        return 0;
      }
      
      for (const [s, _] of combs) {
        // cost has been subsumed.
        if (s == A[i]) {
          return dp[key] = 0;
        }
      }

      // Otherwise, we don't apply the
      // sum and remove the element at
      // the cost of one full reduction.
      return dp[key] = 1;
    }

    // Skip when the element is zero.
    if (A[i] == 0) {
      return dp[key] = g(i - 1, []);
    }
    
    // Reduce this element fully.
    let result = 1 + g(i - 1, [A[i]]);

    // Reduce by a selection of
    // amounts that we pass as
    // options for the next element.
    for (const [s, ks] of combs) {
      if (s == A[i]) {
        result = Math.min(
          result,
          g(i - 1, ks)
        );
      } else {
        result = Math.min(
          result,
          1 + g(i - 1, ks.concat(A[i] - s))
        );
      }
    }
    
    return result;
  }
  
  return g(A.length - 1, []);
}

var inputs = [
  [2, 3, 4, 5, 1, 2, 3, 1, 2, 3], // 8
  [2, 5, 10, 7], // 3
  [4, 9, 11, 6], // 3
  [2, 3, 1], // 2
  [3, 4, 1, 2 ], // 3
  [3, 4, 1], // 2
  [3, 3, 2, 3, 3], // 3
  [2, 5, 0, 2, 5], // 4
  [4, 9, 11, 6, 3, 1, 4] // 5
];

for (const input of inputs) {
  console.log(JSON.stringify(input));
  console.log(f(input));
}

Avoiding jargon, your goal is to zero as many digits as possible each time without splitting the remaining digits more than necessary.

避免使用行话，你的目标是每次尽可能多地将数字归零，而不会超出必要地拆分剩余的数字。

The process is more or less as follows:

这一过程大致如下：

1. Collapse any contiguous number sequences (112233 is the same as 123 in this case).


2. Get all the possible max ranges (likely best handled with recursion to avoid duplicating ranges).


3. Get the count of numbers that can be zeroed in each range and subtract the number of times it occurs in the middle of a range.


4. Choose the range with the largest result from step 3. If there are multiple ranges with the same result, choose the biggest.


5. Subtract the smallest number from all items in the range chosen in step 4.


6. Add 1 to your step count and repeat from step 2 for each range bookended by 0s (or boundaries) until there are none left.

I will try to add some actual c++ code to this answer when I have a chance.

当我有机会的时候，我会尝试在这个答案中添加一些实际的C++代码。