原题地址：https://oj.leetcode.com/problems/word-break/

题意：

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

解题思路：这道题考察的显然不是dfs，为什么？因为这道题不需要给出如何分割的答案，只需要判断是否可以分割为字典中的单词即可。我们考虑使用动态规划，这个思路看代码的话不难，用python写起来也比较清晰。

代码：

class Solution:    # @param s, a string    # @param dict, a set of string    # @return a boolean    # @good coding!    def wordBreak(self, s, dict):        dp = [False for i in range(len(s)+1)]        dp[0] = True        for i in range(1, len(s)+1):            for k in range(i):                if dp[k] and s[k:i] in dict:                    dp[i] = True        return dp[len(s)]