给定一组数字序列，计算可能的解码数量。

Question

给定一组数字序列，计算可能的解码数量。

3

假设我们有一串二进制值的字符串，其中某些部分可能对应于特定的字母，例如：

A = 0
B = 10
C = 001
D = 010
E = 001

例如，如果我们假设字符串为“001010”，我们可以有六个不同的可能性：

AABB
ADB
CAB
CD
EAB
ED

我需要提取出确切的组合数。我正试图从动态规划的角度概念性地解决这个问题，但在子问题的表述和相应矩阵的组合方面遇到了困难。
非常感谢任何正确算法构建的指导。
提前致谢。

- John Mòf

我在动态规划方面有点生疏，但这不是它的适用场景吧？动态规划旨在获得最优结果，而这里有多个结果。此外，我认为您不能使用矩阵，因为A、B、C等长度不同。 - kmdreko

3个回答

1

在解决DP问题时，通常先考虑递归解决方案，然后再考虑将其转换为DP解决方案。

这里的一个不错的递归洞察力是，如果您有一串非空数字，则解码它的任何方式都将以某个单个字符开头。因此，您可以尝试每个字符，查看它是否与开头匹配，并在匹配的情况下计算解码余下字符串的方法数量，从而计算解码该字符串的方法数。

这变成了一个很好的DP问题的原因在于，当您取出一个单独的字符时，您留下的是一串较短的数字字符串，它始终是原始字符串的后缀。因此，想象一下，您制作了一张表格，为原始字符串的每个后缀存储了解码该字符串的方法数。如果您使用上述洞察力从右到左填充该矩阵，则最终通过读取对应于整个字符串的条目来获得最终答案。

看看您能否找到将其转化为具体算法的方法，然后去编写代码。祝你好运！

- templatetypedef

谢谢。我正在尝试从你的角度来聚焦问题：我必须从一个字符的后缀开始，然后考虑两个字符的后缀，以此类推..？但是当我向前缀添加一个字母时，如何避免重新计算所有内容？ - John Mòf

你能详细说明一下“在前缀中添加一个字母”的意思吗？ - templatetypedef

假设有以下字符串“0010”。我考虑每个前缀：0、00、001、0010。当我考虑最后一个（0010，整个字符串）时，我必须将可获得的后缀字符串001的组合数与可以通过添加最后一个字符获得的组合数相加。这样对吗？ - John Mòf

不太对。你会尝试将字符串分割为0|010、00|10、001|0和0010|。你需要使用递归/DP来确定在竖线右侧（后缀）分割字符串的方式数量，然后将所有结果相加。这样说清楚了吗？ - templatetypedef

1

你可以制定一个动态规划的方程，其中f(i) = sum( f(i - j) * count(matches_j) )，对于所有以索引i结尾的长度为j的匹配项，具体取决于输入，您还可以通过为字典创建自定义trie来加快速度，这样您只需要检查相关匹配项（例如，A后跟B后跟D）。以您的例子为例：

f(0) = 1
f(1) = 1 * f(0) = 1
f(2) = 2
f(3) = 1 * f(2) + 1 * f(1) + 1 * f(0) = 4
f(4) = 0
f(5) = 1 * f(4) + 1 * f(3) + 1 * f(2) = 6

- גלעד ברקן

我正在尝试理解你的解决方案。我试图构建一个矩阵，其中行是子问题（长度为i的前缀），列是要测试的每个组合的长度（j = 1、2、3）；但是，如果这是正确的方法，我无法理解如何根据你的公式填充每个单元格[i，j]。 - John Mòf

@JohnMòf 谢谢您的评论。不，我的建议是针对一维DP的。我使用j只是为了方便表示字典按长度分组 - 在您的示例中，这将是[[A]，[B]，[C，D，E]]。对于DP数组中的每个i，您都会遵循我的公式。 j序列只是您正在尝试匹配的当前字典单词的长度。 - גלעד ברקן

例如，在索引0处，您只能匹配A（j = 1）；而在索引3处，您可以匹配A，B，D（j = 1，然后是2，然后是3）。（我在注意到一些错误后编辑了我的答案中的示例；现在应该已经修复了。） - גלעד ברקן

现在我理解了！这是一种具有线性复杂度的最优解决方案，恭喜！唯一我不明白的是（从理论角度来看）：为什么要使用乘法运算符而不是加法运算符在公式 f(i-j)* count(matches_j) 中？在每一步中，您都会重复使用先前计算的子问题；在我的脑海中，我必须对先前的解决方案进行求和。 - John Mòf

1

@JohnMòf 我认为复杂度是 O(n * k)，其中 k 是字典单词的数量，但 k 也取决于字典单词的长度。人们会假设字典中每个 j 只有一个匹配项，在这种情况下，您只需编写 f(i - j) if match_j matches, else 0，但您的字典似乎对相同的子字符串具有多个匹配项（例如，C 和 E 匹配相同的代码）。在这种情况下，您必须进行乘法运算，因为您可以将其中任何一个与字符串中较早的可能性相结合。 - גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1196549 · Accepted Answer

您可以使用一个简单的递归过程：尝试将每个模式与字符串的开头匹配；如果有匹配，则以剩余的字符串递归重复。当字符串为空时，您已经找到了一个解码。

Patterns= ["0", "10", "001", "010", "001"]
Letters= "ABCDE"

def Decode(In, Out):
    global Patterns

    if len(In) == 0:
        print Out
    else:
        for i in range(len(Patterns)):
            if In[:len(Patterns[i])] == Patterns[i]:
                Decode(In[len(Patterns[i]):], Out + Letters[i])

Decode("001010", "")

AABB
ADB
CAB
CD
EAB
ED