Динамическое программирование: количество ходов, чтобы уменьшить массив до 1 числа

Question

Я пытаюсь подойти к проблеме оптимизации с помощью метода заполнения таблицы динамического программирования, но мне не удалось разбить проблему в оптимальных подструктурах.

Это проблема:

С учетом отсортированного массива, начиная с начального элемента, за сколько ходов вы можете уменьшить массив, чтобы иметь только один элемент.

1. Вы можете удалить элемент массива, за исключением начального числа, которое рассматривается как 1 ход, это уменьшает массив.
2. Вы можете добавить элемент массива, который меньше, чем начальное число, в начальное число. Это считается 1 ход.
3. Вы можете добавлять в начальное число, используя предыдущий подход, столько раз, сколько хотите.
4. Семя может "потреблять" любой элемент меньше, чем оно. Это уменьшает массив.

например, это отсортированный массив

3, 20, 50, 100, 400

Первый элемент - это семя.

Первый элемент еще не может использовать следующий больший элемент, поэтому нам нужно добавить к нему. В соответствии с ограничениями мы можем добавить все, что меньше семени, за 1 ход. Итак, допустим, мы добавляем 2.

moves = 1
seed = seed + 2
5, 20, 50, 100, 400

все еще seed не может использовать следующий элемент, поэтому давайте добавим 4

moves = 2
seed = seed + 4
9, 20, 50, 100, 400

moves = 3
seed = seed + 8
17, 20, 50, 100, 400

moves = 4
seed = seed + 16
33, 20, 50, 100, 400

теперь семя может "потреблять" следующий элемент так уменьшенный массив становится

53 (33 + 20) , 50, 100 , 400

53 может потреблять 50 и становиться 103

103, 100, 400

103 может коситься 100 и стать 203

203, 400

203 - это семя, оно не может потреблять 400 так

moves = 5
seed = seed + 202
405, 400

теперь он может потреблять и становиться 805

мы могли бы просто убрать 400, что считается за 1 ход.

всего ходов = 5

Но есть и другое решение: удалить все элементы (20, 50, 100, 400) из массива, что заняло бы 4 хода.

Таким образом, в этом случае минимальное количество ходов равно 4.

Пытаясь думать об этом с точки зрения динамического программирования, я вижу, что на каждом шаге у нас есть 2 варианта: использовать элемент или удалить элемент. Также кажется, что общее количество путей, которое нужно рассмотреть, это все 2 ^ n путей.

но мне не удается разбить его на перекрывающиеся подзадачи или оптимальную подструктуру или даже определить рекуррентное отношение.

Правильное ли здесь динамическое программирование?

Некоторые наблюдения:

1. когда нам нужно что-то добавить к начальному числу, наилучшим подходом, кажется, является добавление максимально возможного допустимого значения, которое является начальным значением - 1 * 1059
2. как только мы решим удалить элемент, это означает, что последующие элементы также будут удалены. Почему, потому что, если мы приняли решение, что многократное добавление к начальному числу бесполезно для текущего элемента, оно будет справедливо и для следующего большего элемента.

Answer 1

Я не вижу в этом проблемы DP.

Вы можете избавиться от наименьшего элемента a, либо удалив его (и все остальное; ваше второе наблюдение верно), либо потребив его.

Удаление займет n ходов, а потребление займет log (a/s) ходов (ход эффективно удваивает семя). Делай, что меньше; если вы решили увеличить семя и потреблять, примените ту же логику к следующему элементу.

Answer 2

Заметьте, что удаления между целевыми потреблениями не имеют смысла, потому что даны начальное число, s и следующие элементы; a, b и c; чтобы иметь возможность потреблять b или c далее, мы обязательно должны увеличить s сначала за a, а затем за b. Но если бы мы увеличили s так далеко, используя ходы "увеличения", это могло бы спасти только наши ходы (и никогда не добавлять ходы), чтобы потреблять a и b на пути к потреблению c. (Я думаю, что вы пришли к аналогичному выводу.)

Таким образом, наше решение, проходящее слева направо, всегда состоит в том, чтобы прекратить увеличивать семя и убрать все с этой точки до конца. Как уже упоминалось, мы можем рассчитать, сколько ходов необходимо для любого необходимого увеличения O(1), наблюдая за данным семенем s и следующим элементом a:

(s - 1) * 2^m + 1 > a
2^m > (a - 1) / (s - 1)
m > log2((a - 1) / (s - 1))

Тогда суммарный обход будет O (n).

Answer 3

Вы можете решить это, используя (max {данный массив} +1) * array_size время и сложность памяти.

int dp[array_size][max{given array}+1]={INF} // initially all index holds infinity
int seed=array[seed_index];
int Max=max{given array}+1;
dp[0][seed]=0; 
for(int i=1;i<=n;i++){  // Consuming or removing ith element
   for(int j=1;j<=Max;j++){ // if the current seed value is j
       //Consider the removing case
       dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
       // Increasing seed value
        dp[i-1][min(Max,j+(j-1))]=min(dp[i-1][min(Max,j+(j-1))],dp[i-1][j]+1);
       // Consider the consuming case
       if(j>array[i]){
          dp[i][min(Max,j+array[i])]=min(dp[i-1][j],dp[i][min(Max,j+array[i])]);  // If j is the current seed value and you want to consume ith element then  after consuming the ith element the seed will be j+array[i] but if it is greater than Max we can take upto max . Because for consuming the maximum value we need only the Max value. 
       }
   }
}

// Now check the smallest possible value for the latest number.
result = INF;
for(int i=0;i<=Max;i++)result=min(result,dp[n][i]);

Здесь dp [i] [j] представляет собой результат уменьшения до i-го значения массива, а после уменьшения до i-го значения вы получите j. И dp [i] [j] будет содержать количество ходов, чтобы уменьшить до i-го значения до 1 элемента с начальным значением j.

В случае потребления:
Если j является текущим начальным значением, и вы хотите использовать i-й элемент, то после использования i-го элемента начальное число будет равно j + array [i], но если оно больше, чем Max, мы можем принять значение Max. Потому что для потребления максимального значения нам нужен только максимум + 1 из максимального {заданного массива}.

Рекурсивный подход:

int dp[array_size][max{given array}+1]={-1} // initially all index holds -1
int Max=max{givenarray}+1;

int DP(int seed,int index){
   if(index==n+1)return 0;
   if(dp[seed][index]!=-1)return dp[seed][index];// previously calculated
   int res=inf;
   // By removing
    res=DP(seed,i+1)+1;
   //Increasing seed
   if(seed<Max)
      res=min(res,1+DP(min(Max,seed+seed-1),index));
   // By consuming
   if(seed>array[i])
      res=min(res,DP(seed+array[i],i+1));
   dp[seed][index]=res;
  return res;
}