由leetcode139题Word Break产生的对动态规划的一点思考。
题目要求是这样的：
Given a stringsand a dictionary of wordsdict,determine ifscan be segmented into a space-separatedsequence of one or more dictionary words.
For example, givens="leetcode",dict=["leet", "code"].
Return true because"leetcode"can be segmented as"leet code".
HideTags
DynamicProgramming
大意是给定一个字符串和一个字典，问该字符串是否在字典中，或由字典中的单词拼接而成。
我的动态规划的版本：
bool wordBreak(string s, unordered_set<string> &dict){int length = s.size();vector<vector<bool>> f(length, vector<bool>(length));//f[i][j]表示从s中从下标i起j+1个字符能否被组合for (int j = 0; j < length; j++)//竖着，一列一列赋值{for (int i = 0; i <= length – j-1; i++){bool flag = false;if (dict.count(s.substr(i, j + 1)) > 0)//截取字符串flag = true;for (int k = 1; k <= j&&!flag; k++)//能否组合出f[i][j]表示的子串，k表示组合中前半段的flag = f[i][k-1] && f[i + k][j – k];f[i][j] = flag;}}return f[0][length-1];}
其中f[i][j]表示从s中从下标i起j+1个字符能否被组合
具体思路就是：
f[i][j]作为一整段位于字典中 或 f[i][j]可以分两段分别能被组合而成
二维数组从左往右从上往下依次被填充。
提交之后发现较平均水准稍慢一点点，网上搜了一下发现第二种动态规划的写法
bool wordBreak(string s, unordered_set<string> &dict){int n = (int)s.size();vector<bool> dp(n + 1, false);dp[0] = true;for (int i = 0; i < n; i++){if (dp[i]){for (int len = 1; i + len – 1 < n; len++)if (dict.count(s.substr(i, len)) > 0)dp[i + len] = true;}}return dp[n];}
仔细对比了一下，发现解法一虽然没有重复计算，但有无用计算。解法二是比解法一更优的方案，没有无用计算。
解法一中，要判断f[i][j]，必须知道每一个f[i][k-1]和f[i + k][j – k]（其中1<=k<=j），，所以将二维数组f想象成一个矩形，要填充一个格子，必须事先计算它左下方的所有格子（越界的格子当然不算）的值。
当所有格子都填充完毕后，解法一实际上已经求出了s的所有子串是否能由字典中的词组合而成。而题目只要求判断s，仔细分析，发现解法一存在无用计算：
对于字符串s，当它的前半段已经求出不能由字典中词组合而成时，就没必要对后半段进行检查了。因为s是确定唯一的，这种组合已经不可能构成s。若是不唯一的，则检查后半段可用于其他组合。
而解法二就利用了这一点，当且仅当前半段能组合而成，才对后面可能的组合进行检查，避免了无用计算。
请打开窗口，让我的灵魂与你的灵魂相拥。
