精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
一员工在公司工作了8年被裁，赔偿了22万，刚找到工作，结果前公司就想通过涨薪的方式让他继续回来上班，并且把赔偿金还回去。回去上班可以，为什么要还赔偿金，万一还了之后不到一个月开除，岂不是啥赔偿都没了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第139：单词拆分。
问题描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同
问题分析
定义dp[i]表示字符串的前 i 个字符经过拆分是否都存在于字典wordDict中。如果求dp[i]，需要往前截取 k 个字符，判断子串[i-k+1，i]是否存在于字典wordDict中，并且前面子串[0，i-k]拆分的子串也是否都存在于wordDict中，如果都存在，说明可以拆分
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
boolean[] dp = new boolean[len + 1];
dp[0] = true;// 空字符串，不需要字典中的字符串。
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
// 把字符串分割为s[0,j-1]和s[j,i]两部分，
// 这两部分必须都存在于字典中dp[i]才会返回true。
dp[i] = dp[j] && wordDict.contains(s.substring(j, i));
if (dp[i])// 只要有一种方式能够拆分成功，后面就不要尝试拆分了。
break;
}
}
return dp[len];
}
public:
bool wordBreak(string s, vector<string> &wordDict) {
size_t len = s.size();
vector<bool> dp(len + 1, false);
unordered_set<std::string> wordSet(wordDict.begin(), wordDict.end());
dp[0] = true;// 空字符串，不需要字典中的字符串。
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
// 把字符串分割为s[0,j-1]和s[j,i]两部分，
// 这两部分必须都存在于字典中dp[i]才会返回true。
if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
dp[i] = true;// 只要有一种方式能够拆分成功，后面就不要尝试拆分了。
break;
}
}
}
return dp[len];
}
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
len_s = len(s)
dp = [False] * (len_s + 1)
dp[0] = True # 空字符串，不需要字典中的字符串。
for i in range(1, len_s + 1):
for j in range(i):
# 把字符串分割为s[0,j-1]和s[j,i]两部分，
# 这两部分必须都存在于字典中dp[i]才会返回true。
if dp[j] and s[j:i] in wordDict:
dp[i] = True
# 只要有一种方式能够拆分成功，后面就不要尝试拆分了。
break
return dp[len_s]
数组，稀疏表(Sparse Table)，单向链表，双向链表，块状链表，跳表，队列和循环队列，双端队列，单调队列，栈，单调栈，双端栈，散列表，堆，字典树(Trie树)，ArrayMap，SparseArray，二叉树，二叉搜索树(BST)，笛卡尔树，AVL树，树堆(Treap)，FHQ-Treap，哈夫曼树，滚动数组，差分数组，LRU缓存，LFU缓存
……
图的介绍，图的表示方式，邻接矩阵转换，广度优先搜索(BFS)，深度优先搜索(DFS)，A*搜索算法，迭代深化深度优先搜索(IDDFS)，IDA*算法，双向广度优先搜索，迪杰斯特拉算法(Dijkstra)，贝尔曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓扑排序，约翰逊算法(Johnson)
……
