Зараженная рыба может съесть другую рыбу меньшего размера, чем ее собственная. Требуется минимальное количество операций

Вы можете повысить эффективность, немного изменив свой алгоритм.

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

Когда вы едите рыбу, вы становитесь больше без каких-либо затрат.

Следовательно, альтернативы:

• Ешьте следующую рыбу после взросления, т.е. после добавления новых рыб
• Избавьтесь от всех оставшихся рыб

Тогда формулу можно упростить следующим образом, оставив остальные коды без изменений:

return Math.min(count(curr, a, i, op+1), op + a.length -1 - i);

В этом случае вам не нужна мемоизация: функция count работает только в одном направлении, всегда увеличивая свои внутренние значения.

Примечание. Я предполагаю, что рыбы отсортированы, как указано в вашем коде.

Сложность, без учета сортировки: O(n + log(weight_max/weigth_in))

РЕДАКТИРОВАТЬ: есть еще один способ ускорить процесс:

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

Как ответили другие, здесь могут работать жадные. После первого поедания всей более мелкой рыбы каждый пункт выбора: (1) добавить максимально возможную рыбу меньше, чем текущая голодная рыба, или (2) удалить всю рыбу одинакового или большего размера. Ясно, что удалять рыбу из середины не нужно, поскольку, если бы мы могли съесть рыбу покрупнее, мы могли бы съесть и эту.

Состояние, которое мы хотели бы оптимизировать, это num_current_moves + num_removals_needed. Но поскольку нам нужна только одна переменная для хранения наиболее часто встречающегося такого состояния, мы можем обновлять ее после каждого выбора, перебирая отсортированный список, жадно добавляя рыбу. Вариант (2) не является активным изменением; скорее, это просто часть расчета наилучшего видимого состояния в каждой точке.

Итеративный код JavaScript:

function f(x, A){
  A.sort((a, b) => a - b)
  
  let sum = x
  let removals_needed = A.length
  let moves = 0
  let best = removals_needed
  let i = 0
  
  while (i < A.length){
    if (sum > A[i]){
      sum = sum + A[i]
      removals_needed = removals_needed - 1
      i = i + 1

    // It might not be worth
    // trying to grow the fish,
    // but the growth rate is 
    // probably fast enough not
    // to add significant time
    } else {
      sum = sum + (sum - 1)
      moves = moves + 1
    }
    
    best = Math.min(best, moves + removals_needed)
  }
  
  return best
}

var inputs = [
  [10, [9,20,25,100]], // 2
  [3, [25,20,100,400,500]], // 5
  [3, [20,21,22,23,24,25]], // 4
  [3, [20,21,22]], // 3
  [50, [25,20,9,100]] // 0
]

for (let [x, A] of inputs){
  console.log(`${x} -> ${A}`)
  console.log(f(x, A))
  console.log("")
}

Подведем итог:

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

Зараженная рыба может сожрать всех более мелких рыб, каждый раз увеличиваясь на размер съеденной рыбы.

Вы хотите, чтобы минимальное количество вмешательств оставил только пожиратель.

Гораздо проще алгоритм:

1. Отсортируйте всех обычных рыб по размеру.
2. Тривиальное решение — удалить всех рыб вручную.
3. Вы еще не добавили новых рыб.
4. Пожирайте самых маленьких рыбок как можно дольше.
5. Новое решение-кандидат — добавленные рыбы плюс оставшиеся рыбы. Выберите лучший.
6. Если рыбы не осталось, все готово.
7. Увеличьте пожирателя до 2*размера-1, добавляя рыбу размера-1 так часто, как это необходимо, чтобы пожирать самую маленькую рыбу.
8. Продолжайте с шага 4, пожирая рыбу.