为什么分词需要动态规划？

Question

我指的是这个问题：

Given a dictionary, i.e., a set of strings, and a string s, design an efficient algorithm that checks whether s is the concatenation of a sequence of dictionary words. If such a concatenation exists, your algorithm should output it.

这是我在不使用 DP 的情况下解决它的方法：

def getwords(s, start = 0):
  # Find a valid word as a prefix, and try to made the rest work
  for i in range(start + 1, len(s) + 1):
    prefix = s[start:i]
    if isind(prefix):
      # We used the whole thing, but it's a word!
      if i == len(s):
        return [prefix]
      words = getwords(s, i)
      if words:
        return [prefix] + words

  # We made it to the end without finding a word configuration
  return False

DP 算法已记录 here，并在书中 "Elements of Programming Interviews"。我的问题是：为什么？

我找不到我的非 DP 解决方案重新计算相同子问题的任何实例。谁能解释一下为什么这个算法不如DP算法？

Answer 1

(副词qqqqqqqqqqq)
广告，动词，(qqqqqqqqqqq)
副词,(qqqqqqqqqqq)

会有两次 getwords('adverbqqqqqqqqqqq', 6) 调用，不是吗？

如果你有这样的东西，它会变得非常讨厌：

adverbhamstringadverbhamstring...adverbhamstringhorsepowerqqq

Answer 2

据我了解，如果你有一个单词 w 和 n 个字母，并且 w[0:n-1] 中有 k 个有效的单词组合（即 w[0:n-1] 可以拆分成有效词，在不同的地方，k 次），你会在字典中查找 w[n] k 次（假设 w[n] 不是当然是一个有效的词）。这是 ozangds 在他的回答中显示的内容。

使用动态规划方法，由于您只跟踪字符串有效之前的索引（可以拆分为单词），因此您只会查找 w(n) 一次。

在您发布的 link 中查找 TulsiRam 和 geekyandgirly 的评论，它们有助于理解问题的两面。

为什么分词需要动态规划？

Why does word segmentation require dynamic programming?

python

dynamic-programming