描述如下：
"话说有个魔法字典，其中记录了一些魔力单词（字符串），如果一个句子（也是字符串）可以被完全分解为若干魔力单词的拼接，那么这个句子就是一条咒语。假设我们可以用常数时间查询魔力字典是否包含一个特定的单词，那么现在给你一个句子，让你写一个程序判断这个句子是否一条咒语。用动态规划可以解哦。"
其中跟贴的有人说到需要先列出“状态转移方程”，我不太懂，不过觉得这个问题倒是可以用回溯法尝试一下。
代码如下：
#coding: utf-8
#2008-8-21, Neil Chen
# 判断一个句子是否为咒语（由魔法词组成）
# 解法：回溯法
# 魔法词典
magic_words = [’m’, ’foo’, ’bar’, ’boo’, ’barr’, ’jac’, ’j’ ’c’]
# 是否为魔力单词
def is_magic_word(word):
return word in magic_words
# 是否为咒语
def is_spell(sentence):
# 最终如能成功分割为魔法单词，则句子中会出现 n 个分隔点，
# 现尝试用回溯法来找出这些点的位置
split_points = [1]
n = len(sentence)
while True:
# 判断最后两个分隔点之间的单词是否为魔力单词，否则将该位置增加1，继续尝试
is_magic = False
while split_points[-1] <= n:
if len(split_points) == 1:
start = 0
else:
start = split_points[-2]
# 得到最后两个分隔点之间的单词
word = sentence[start : split_points[-1]]
if is_magic_word(word):
is_magic = True
break
else:
split_points[-1] += 1
# 最后一个分隔点之前都是魔力单词
if is_magic:
# 已经到达末尾，成功了
if split_points[-1] == n:
return True
# 增加下一个分隔点位置，继续分割
else:
split_points.append(split_points[-1] + 1)
# 最后一个分隔点无论怎样选都不能组成一个魔力单词，则需要回溯到上一个分隔点
else:
# 退无可退！表示这个句子不是咒语
if len(split_points) == 1:
return False
# 退回到上一个分隔点
else:
split_points.pop()
# 将回溯到的位置加一，重新进入下一次循环尝试
split_points[-1] += 1
#=== 测试代码 ===
if __name__ == ’__main__’:
print is_magic_word(’foo’) # True
print is_magic_word(’fo’) # False
print is_spell(’morning’) # False
print is_spell(’hello’) # False
print is_spell(’foo’) # True
print is_spell(’bar’) # True
print is_spell(’barfoombarmjac’) # True
以上代码已经实现了这个算法。（不过有个小小的问题，如果字符串里含有中文，则不能正确判断，这是因为 python 中 len() 函数判断中文为双字节造成的，等有时间再改进这个）。
3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.com/exam/
