时间戳

首页 > 解决方案 > 动态编程 - 可能的密码数量

python - 动态编程 - 可能的密码数量

问题描述

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

给定单词列表和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。我被困在如何填写表格以考虑单词组合。

标签： pythondynamic-programming

解决方案

您应该tbl[i]使用 length 存储最大数量的可能密码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]

推荐阅读