Головоломка с динамическим программированием: найдите самые длинные последовательные пары из 3 (разных) частей

Question

Головоломка: Xsquare And Chocolates Bars

Мой подход:

3 предмета из 1 набора.
Необходимо найти самые длинные последовательные наборы, чтобы всекусочки в наборе не совпадают.
Затем вычтите это из общей длины плитки шоколада.

Начните с индекса 1 (на основе 0).

Разделите

Случай 1 : Если части совпадают, не учитывайте текущий индекс.
Поиск по следующему индексу.

if bar[current - 1] == bar[current] and bar[current] == bar[current + 1]:
    if dp[current + 1] == -1:
        dp[current + 1] = CountConsecutiveSets(current + 1)
    dp[current] = dp[current + 1]
    return dp[current]

---

Случай 2 : Еслиштуки разные
Случай 2.1 : Рассмотреть текущий набор: Счет 1 для текущего набора и найти количество оставшихся наборов после текущего набора.

if dp[current + 3] == -1:
    dp[current + 3] = CountConsecutiveSets(current + 3)
withCurrent = 1 + dp[current + 3]

Случай 2.2 : игнорировать текущий набор: найти остальные наборы из следующего текущего

if dp[current + 1] == -1:
    dp[current + 1] = CountConsecutiveSets(current + 1)
withoutCurrent = dp[current + 1]

Поскольку необходимо найти максимальный последовательный набор, найдите max(Case 2.1 & Case 2.2).

---

Базовый случай:

Когда ток находится на последнем индексе (или больше, чем последний индекс), набор не может быть сформирован.
Итак, верните 0.

---

---

Full Coде * * * 1046 1047 1049 контрольный пример: 1052 * бар = "CCCSCCSSSCSCCSCSSCSCCCSSCCSCCCSCCSSSCCSCCCSCSCCCSSSCCSSSSCSCCCSCSSCSSSCSSSCSCCCSCSCSCSSSCS"
Ans: 39 Но выше код дает 6. Что не так в моем мышлении и как это исправить? גלעד ברקן's Сверху вниз логика: def CountRemainingCandies(self, bar): dp = [-1] * len(bar) def CountConsecutiveSets(current): # Solve small sub-problems if current <= 1: dp[0] = dp[1] = 0 return 0 # Divide # Case 1: Consider current # If different candies withCurrent = -1 if bar[current] != bar[current - 1] or bar[current] != bar[current - 2]: if current - 3 < 0: current = 0 if dp[current - 3] == -1: dp[current - 3] = CountConsecutiveSets(current - 3) withCurrent = 1 + dp[current - 3] # Case 2: Ignore current if current - 1 < 0: current = 0 if dp[current - 1] == -1: dp[current - 1] = CountConsecutiveSets(current - 1) withoutCurrent = dp[current - 1] # Combine dp[current] = max(withCurrent, withoutCurrent) return dp[current] consecutiveSetsCount = CountConsecutiveSets(len(bar) - 1) return len(bar) - 3 * consecutiveSetsCount Я использую логику גלעד ברקן, но все еще получаю неправильный ответ для теста
bar = "CCCSCCSSSCSCCSCSSCSCCCSSCCSCCCSCCSSSCCSCCCSCSCCCSSSCCSSSSCSCCCSCSSCSSSCSSSCSCCCSCSCSCSSSCS"

Answer 1

Здесь работает нисходящий в Python (f(str, i) возвращает кортеж, (overall_best, sequence_length_up_to_i):

# Returns the sequence length,
# not the problem answer, which
# is the length of the chocolate
# after removing the sequence.
def f(s, i, memo):
  if i in memo:
    return memo[i]

  if i < 2:
    return (0, 0)

  (best, _) = f(s, i-1, memo)

  if s[i] != s[i-1] or s[i] != s[i-2]:
    seq_len = 3 + f(s, i - 3, memo)[1]
  else:
    seq_len = 0

  memo[i] = (max(best, seq_len), seq_len)
  return memo[i]

s = "CCCSCCSSSCSCCSCSSCSCCCSSCCSCCCSCCSSSCCSCCCSCSCCCSSSCCSSSSCSCCCSCSSCSSSCSSSCSCCCSCSCSCSSSCS"

print(f(s, len(s) - 1, {})[0]) # 51

Answer 2

Поскольку последовательность должна быть построена из точных блоков из трех, мы можем рассматривать каждый квадрат как третий в последнем блоке последовательности. Обратите внимание, что мы также можем уменьшить пространство до O(1), обновив только четыре ячейки.

Код JavaScript:

// Returns the sequence length,
// not the problem answer, which
// is the length of the chocolate
// after removing the sequence.
function f(s){
  if (s.length < 3)
    return 0

  let dp = new Array(s.length+1).fill(0)
  let best = 0
  
  for (let i=2; i<s.length; i++){
    if (s[i] != s[i-1] || s[i] != s[i-2])
      dp[i+1] = 3 + dp[i-2]
      
    best = Math.max(best, dp[i+1])
  }
  
  return best
}

var strs = [
  "SSSSSSSSS", 
  "CCCCCCCCC",
  "SSSSCSCCC",
  "SSCCSSSCS",
  "CCCSCCSSSCSCCSCSSCSCCCSSCCSCCCSCCSSSCCSCCCSCSCCCSSSCCSSSSCSCCCSCSSCSSSCSSSCSCCCSCSCSCSSSCS"
]

for (let s of strs)
  console.log(f(s))