这个自上而下的动态编程代码的时间复杂度是多少？
What is the time complexity of this top down dynamic programming code?
我无法像下面的例子那样分析自上而下的动态规划方法的时间复杂度。你能帮帮我吗？
Problem : Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
bool match(string &s,int l,int n,string &wordDict) {
int i = 0;
while(l < n && i < wordDict.size()) {
if (s[l] != wordDict[i])
return false;
l++;
i++;
}
return i == wordDict.size();
}
bool wordBreakUtil(string &s, int l, int n, vector<string>& wordDict, map<int,bool> &m) {
if (l==n)
return true;
if (m.find(l) != m.end()) {
return m[l];
}
int i;
for(i=0;i<wordDict.size();i++) {
if (match(s,l,n,wordDict[i])) {
if (wordBreakUtil(s,l+wordDict[i].size(),n,wordDict,m))
return true;
}
}
m[l] = false;
return false;
}
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
map<int,bool> m;
return wordBreakUtil(s,0,n,wordDict,m);
}
通过将递归调用内部完成的计算工作与其他工作分开，可以找到记忆 DP 算法的最坏情况界限。具体我们需要确定：
- 使用不同的输入（参数值）调用递归函数的最大可能次数 -- 这是函数必须执行的最大可能次数“做它的工作”而不是快速返回一个已经计算好的答案。
- 每次调用递归函数内部完成的最大工作量，不包括内部对自身的递归调用。
然后我们可以将 (1) 的答案乘以 (2) 的答案以获得上限。 （这个界限可能并不严格，因为问题中可能存在结构，这意味着实际上避免了渐近重要的递归函数调用次数，或者每次调用中完成的工作量远小于渐近递归函数调用的最大可能数量这些调用的重要部分，或两者兼而有之——但实际上它通常很紧。）
不同递归调用的最大数量
递归函数 wordBreakUtil() 被调用时有 6 个不同的参数，但实际上只有其中一个参数 l 随每次调用而变化。因为我们在 m 中记忆结果，所以当我们处理 l 的值时，我们保证我们只让它到达函数的主体（for 循环）我们以前从未见过：这意味着 (1) 的答案是 distinct l 值的最大数量 wordBreakUtil() 可能被调用with，它只是 n + 1（值 0、1、2、...、n）。渐近这是 O(n)。
每次调用中完成的最大非递归工作量
假设字典中有 k 个单词。在 wordBreakUtil() 内，它所做的最大工作量 不包括 在对自身的递归调用中，是 O(kn)。这是因为它循环 k 次，每次调用 match()，并且 match() 在其循环中最多需要 n 步。 （您可以将 match() 的复杂性描述为 L，其中 L 是字典中任何字符串的最大长度，或者您可以更准确地描述为 min(n, L) ，但添加 L 参数会使表达式更复杂，而不会提供太多信息。）还有一个 log k 附加项用于 m.find(l) 调用，但这由 O(kn ) 项，所以在 wordBreakUtil() 中完成的非递归工作仍然是 O(kn).
这意味着整体执行时间受 O(kn^2) 限制。
我无法像下面的例子那样分析自上而下的动态规划方法的时间复杂度。你能帮帮我吗？
Problem : Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Input:
s = "catsandog",wordDict = ["cats","dog","sand","and","cat"]
Output:falseInput:
s = "leetcode",wordDict = ["leet","code"]
Output:true
bool match(string &s,int l,int n,string &wordDict) {
int i = 0;
while(l < n && i < wordDict.size()) {
if (s[l] != wordDict[i])
return false;
l++;
i++;
}
return i == wordDict.size();
}
bool wordBreakUtil(string &s, int l, int n, vector<string>& wordDict, map<int,bool> &m) {
if (l==n)
return true;
if (m.find(l) != m.end()) {
return m[l];
}
int i;
for(i=0;i<wordDict.size();i++) {
if (match(s,l,n,wordDict[i])) {
if (wordBreakUtil(s,l+wordDict[i].size(),n,wordDict,m))
return true;
}
}
m[l] = false;
return false;
}
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
map<int,bool> m;
return wordBreakUtil(s,0,n,wordDict,m);
}
通过将递归调用内部完成的计算工作与其他工作分开，可以找到记忆 DP 算法的最坏情况界限。具体我们需要确定：
- 使用不同的输入（参数值）调用递归函数的最大可能次数 -- 这是函数必须执行的最大可能次数“做它的工作”而不是快速返回一个已经计算好的答案。
- 每次调用递归函数内部完成的最大工作量，不包括内部对自身的递归调用。
然后我们可以将 (1) 的答案乘以 (2) 的答案以获得上限。 （这个界限可能并不严格，因为问题中可能存在结构，这意味着实际上避免了渐近重要的递归函数调用次数，或者每次调用中完成的工作量远小于渐近递归函数调用的最大可能数量这些调用的重要部分，或两者兼而有之——但实际上它通常很紧。）
不同递归调用的最大数量
递归函数 wordBreakUtil() 被调用时有 6 个不同的参数，但实际上只有其中一个参数 l 随每次调用而变化。因为我们在 m 中记忆结果，所以当我们处理 l 的值时，我们保证我们只让它到达函数的主体（for 循环）我们以前从未见过：这意味着 (1) 的答案是 distinct l 值的最大数量 wordBreakUtil() 可能被调用with，它只是 n + 1（值 0、1、2、...、n）。渐近这是 O(n)。
每次调用中完成的最大非递归工作量
假设字典中有 k 个单词。在 wordBreakUtil() 内，它所做的最大工作量 不包括 在对自身的递归调用中，是 O(kn)。这是因为它循环 k 次，每次调用 match()，并且 match() 在其循环中最多需要 n 步。 （您可以将 match() 的复杂性描述为 L，其中 L 是字典中任何字符串的最大长度，或者您可以更准确地描述为 min(n, L) ，但添加 L 参数会使表达式更复杂，而不会提供太多信息。）还有一个 log k 附加项用于 m.find(l) 调用，但这由 O(kn ) 项，所以在 wordBreakUtil() 中完成的非递归工作仍然是 O(kn).
这意味着整体执行时间受 O(kn^2) 限制。