动态规划之谜：寻找3个（不同）片段的最长连续对

Question

拼图：Xsquare And Chocolates Bars

我的方法：

一套3件。
需要找出最长的连续集合，以便集合中的所有片段都不相同。
然后从巧克力棒的总长度中减去这个。你知道吗

从索引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。你知道吗

---

---

完整代码

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=“cccscssscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscs 答案：39

但上面的代码给出了6。你知道吗

我的想法有什么问题&如何解决？你知道吗

---

---

---

---

גלעדברקן的Top-Down逻辑：

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

因为序列必须由三个完全相同的块组成，我们可以把每个正方形看作序列最后一个块中的第三个。注意，我们还可以通过只更新四个单元格来将空间减少到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)返回一个元组，(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