<p>因为序列必须由三个完全相同的块组成,我们可以把每个正方形看作序列最后一个块中的第三个。注意,我们还可以通过只更新四个单元格来将空间减少到<code>O(1)</code>。你知道吗</p>
<p>JavaScript代码:</p>
<p/><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
;
<div^{cl2}$
;
<pre class="snippet-code-js lang-js prettyprint-override"><code>// 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))</code></pre>
;
</div>
;
</div>
;