擅长:python、mysql、java
<p>这是一个很好的例子,你想用动态编程。实现这个算法有很多种方法,下面我来画一个(不是最佳的)。在</p>
<p>对于每个前缀长度(0到N),您可以记住该前缀所能达到的最佳分数。显然,长度为0的前缀的最佳分数是0。您可以用减号来初始化其他前缀(每个字符加1分)。在</p>
<p>现在,迭代这些位置,并尝试匹配该位置的所有字典单词(我们称之为K)。如果有匹配项,则将位置(K+匹配单词的长度,我们称之为L)处的最佳分数更新为max(scores[L],scores[K]+word_score)。最终结果将是位置分数[len(string)]。在</p>
<pre><code>def get_score(dct, to_score):
dp = [-i for i in xrange(len(to_score) + 2)]
for i in xrange(len(to_score)):
for word in dct:
lw = len(word)
if lw <= len(to_score) - i:
if word == to_score[i:i + lw]:
dp[i + lw] = max(dp[i+lw], dp[i] + dct[word])
dp[i + 1] = max(dp[i + 1], dp[i] - 1)
return dp[len(to_score)]
dct = {"fe": 1, "je": 2, "jee": 3, "ain": 3, "dai": 5, "ne": 2, "ai": 2}
for s in ("feaineai", "fejebain", "aidaidai"):
print "%s -> %d" % (s, get_score(dct, s))
</code></pre>