动态规划 - 可能的密码数量

Question

我有一个动态规划问题。我觉得很难，所以我希望能得到一些帮助。

给定单词列表和密码长度 n，我想知道可能的密码组合数量。密码可以是长度为 n 的单个单词，也可以是 由下划线分隔的单词组合 。

例如，passwords(5, ["house, "no"]) = 2 因为可能的密码是“house”和“no_no”。

到目前为止我尝试过的：

def voc_to_list(vocabulary):
    """
    produces a list lengths such that lengths[i] is the number of
    words of length i in vocabulary
    """
    max_len = max([len(w) for w in vocabulary])
    lengths = [0] * (max_len + 1)
    for w in vocabulary:
        wordLength = len(w)
        lengths[wordLength] += 1
    return lengths


def passwords(L, vocabulary):
    lengths = voc_to_list(vocabulary)
    k = len(lengths)
    tbl = [0] * (L + 1)
    for i in range(L + 1):
        if i < k:
            tbl[i] = lengths[i]
        for j in range(min(i, k)):
            # This is where I am stuck
            tbl[i] += ??
    return tbl[L]

里面tbl[i]我已经有长度i的话了。我被困在如何填写 table 以考虑单词的组合。

Answer 1

您应该在 tbl[i] 中存储长度为 i 的最大可能密码数，您已经知道了。更新步骤涉及组合学。一个简单的例子是 passwords(9, ["a", "e", "i", "o", "u"]) == 5**5。如果这对您来说不直观，我建议重新访问所需的数学。

因此，更新步骤实际上是最大组合数tbl[i-j-1]的乘积之和和将密码长度“补全”为的新词候选那一点lengths[j]。为此，您迭代更新：

def passwords(L, vocabulary):
    lengths = voc_to_list(vocabulary)
    k = len(lengths)
    tbl = [0] * (L + 1)
    for i in range(L + 1):
        if i < k:
            tbl[i] = lengths[i]
        for j in range(1, min(i-1, k)):
            tbl[i] += tbl[i-j-1] * lengths[j]  # -1 due to underscores
    return tbl[L]

动态规划 - 可能的密码数量

Dynamic programming - number of possible passwords

python

dynamic-programming