擅长:python、mysql、java
<p>下面是Python中自上而下的工作(<code>f(str, i)</code>返回一个元组,<code>(overall_best, sequence_length_up_to_i</code>):</p>
<pre><code># 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
</code></pre>