擅长:python、mysql、java
<p>在处理字符串上的动态编程时,“我的子问题应该是什么”的答案通常是前缀、后缀或子字符串</p>
<p>从你最后的笔记中,你已经正确地认识到我们可以通过解决后缀问题来解决原来的问题。我们还知道,我们的子问题必须知道剩下要使用的工件数量。此时,我们可以猜测子问题是什么,并尝试定义一个公式</p>
<p>我们可以让<code>f(i,j,k)</code>成为使用<code>S</code>的最后<code>i</code>个字母精确地<code>k</code>子字符串来匹配<code>U</code>的最后<code>j</code>个字母的方法数。什么是边缘案例?如果<code>j</code>和<code>k</code>都是0,我们就没什么关系了;有一种方法可以什么都不做。如果<code>i<j</code>我们无法匹配<code>j</code>个字母,如果<code>j<k</code>我们无法将<code>j</code>个字母分割成足够的片段</p>
<p>最后,您必须定义主递归。首先,我们可以跳过<code>S</code>的这个字母,它将<code>f(i-1,j,k)</code>作为求和。现在,让<code>Match-Length(i,j)</code>为<code>S[-i:]</code>开头与<code>U[-j:]</code>匹配的连续位置数。我们需要添加所有可能的匹配项:对于每个长度<code>l</code>,<code>1 <= l <= Match-Length(i,j)</code>,我们必须添加<code>f(i-l, j-l, k-1)</code>。这包括所有情况</p>
<p>编辑:用户qouify发布了一个更好的解决方案。此DP公式的直接翻译在时间<code>O(|S| |U|^2 m)</code>中运行,而他们的直接翻译在时间<code>O(|S| |U| m)</code>中运行。可以修改我的公式以匹配该运行时,但您需要计算前缀和,以便在预处理和记忆后的<code>f(i-l, j-l, k-1)</code>时间内可以找到<code>O(1)</code>的每个和</p>