动态规划难题：找到最长的连续对 3（不同）件

Question

我的做法：

3件为1套
需要找出最长的连续集合，使得集合中的所有片段都不相同。
然后从巧克力棒的总长度中减去它。

从索引 1 开始（基于 0）。

划分

情况一：如果片段相同，则不考虑当前索引。
从下一个索引查找。

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)。

基本案例：

当前在最后一个索引处（或大于最后一个索引）时，无法形成集合。
所以 return 0.

完整代码

def CountRemainingCandies(self, bar):
    dp = [-1] * (len(bar) + 2)

    def CountConsecutiveSets(current):
        # Solve small sub-problems
        if current >= len(bar) - 1:
            dp[current] = 0
            return 0

        # Divide
        # Case 1: If same candies
        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]

        # Case 2: If different candies
        # Case 2.1: Consider current
        if dp[current + 3] == -1:
            dp[current + 3] = CountConsecutiveSets(current + 3)
        withCurrent = 1 + dp[current + 3]
        # Case 2.2: Ignore current
        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(1)
    return len(bar) - 3 * consecutiveSetsCount

测试用例：

bar = "CCCSCCSSSCSCCSCSSCSCCCSSCCSCCCSCCSSSCCSCCCSCSCCCSSSCCSSSSCSCCCSCSSCSSSCSSSCSCCCSCSCSCSSSCS"
答：39

但是上面的代码给出了 6。

我的想法有什么问题以及如何解决？

阿拉伯语的逻辑：

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

由于序列必须由三个块组成，我们可以将每个方块视为序列最后一个块中的第三个方块。请注意，我们还可以通过仅更新四个单元格将 space 减少到 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))

Answer 2

这是在 Python 中自上而下的工作（f(str, i) returns 一个元组，(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

动态规划难题：找到最长的连续对 3（不同）件

Dynamic Programming puzzle: Find longest consecutive pairs of 3 (different) pieces

python

recursion

dynamic-programming

memoization

划分

基本案例：

完整代码