之前刷LeetCode。碰到了这道题。
一开始没想到要用动态规划来解。
后来看了一下答案给的代码，又仔细研究了一下，发现确实是动态规划。
中途看了很多其他人的博客解释，都没把动态规划讲清楚。
所以干脆就自己来写一份详解吧。
首先，把题目贴上来
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"
.
简单来说，就是s能不能由dict中存储的单词拼出来。
注意了，这里有陷阱。不能简单的从前往后substr递增的检查是否包含在dict中，否则会有问题。
比如 s=“aaaaaaa” dict=[“aaa”,”aaaa”]
这种例子如果用递增的检查，会把s检测成 aaa aaa a ，最终返回false。而这个例子是返回true的。所以错了。
下面开始介绍怎么用动态规划来讲。
总的来说，动态规划一般有2个步骤。1.把原问题划分成若干子问题 2.已经计算过的问题可以被后面的问题利用从而减少重复计算。
该说的都说了，接下来到实际问题里面去体会。
先贴出官网给出的标准答案
bool wordBreak(string s, unordered_set<string> &dict)
{
vector<bool> flag(s.length()+1,false);
flag[0] = true;
for (int i = 1; i < s.length()+1; ++i)
{
for (int j = i - 1; j >= 0; j--)
{
if (flag[j] && dict.count(s.substr(j, i-j)) != 0)
{
flag[i] = true;
break;
}
}
}
return flag[s.length()];
}简单讲一下这里是怎么利用动态规划的。
首先
vector<bool> flag(s.length()+1,false);
这个容器的作用，就是前面讲的2. 也就是已经计算过的问题可以被后面的问题所利用，减少重复计算。
具体怎么做的等会再说。
这里的第一层 i 循环，其实就是我们刚才讲的1，也就是子问题。
你可以理解为 i 从1一直到s.length() ，分别表示从下标0开始，长度为1的子问题，长度为2的子问题，……，长度为s.length()的子问题。
而长度为s.length()的子问题的解，其实也就是原问题的解了。
现在再来解释flag数组。
可以理解为 flag[i]==true表示长度为i的子问题是可以成功被划分的。
现在假设已经有 flag[i]==true，即长度为 i 的子问题是可以被划分的。现在已经遍历到 i+x 长度的子问题。
然后由语句：
if (flag[j] && dict.count(s.substr(j, i-j)) != 0)
{
flag[i] = true;
break;
}遍历到j==i时 也就是 flag[j]==flag[i] 由我刚才的假设知 ==true，即 长度为 i 的子问题是可以被划分的
并且有s.substr(j,i-1) 这个子串包含在 dict中。
所以长度为j的子问题现在就可以被划分成 长度为i的子问题+s.substr(j,i-1) 。
所以 长度为 j 的子问题是可以被划分的，也就可以break了。
这样，是不是就利用了前面 子问题i 的计算结果避免了重复计算 子问题i呢。
至此，整个动态规划的思想就讲完了。
我自己又写了一个递归版本的答案，如果你对上面的似懂非懂的话，可以参考一下我的答案。
vector<bool> *flag;
bool fun(string s, unordered_set<string> &dict, int i)
{
if (i == 0 && (*flag)[0] == false)
return dict.find(s) != dict.end();
while (i > 0 && (dict.find(s.substr(i, s.length() - i)) == dict.end()||(*flag)[i]==true))
{
i--;
}
if (i == 0 && dict.find(s.substr(i, s.length() - i)) == dict.end())
return false;
else
if (i == 0)
return true;
(*flag)[i] = true;
return fun(s.substr(0, i), dict, i-1) || fun(s, dict, i);
}
bool wordBreak(string s, unordered_set<string> &dict)
{
if (s.length() == 0)
return false;
vector<bool> mflag(s.length(), false);
flag = &mflag;
return fun(s, dict, s.length()-1);
}简单给点提示，因为要递归，所以flag 数组需要放在全局变量。
整个递归核心部分是那个fun 函数。
最简单的解释就是看它的return语句。返回两个递归的结果。分别表示从后往前 s.length()-i长度的这个子串是答案的解或者它不是答案的解。（有时候s的子串包含在dict中但不是答案的解，见上面的 aaa aaa a 这种分法）
是解，或者不是解，包含了所有可能的情况。因此分成了两种子问题。再加上全局变量flag避免重复计算。
因此满足了动态规划的所有步骤。得到的也是正确答案。