动态规划 - 算法修文，其中的所有标点符号缺失 [英] Dynamic programming - Algorithm to repair text where is all punctuation missing
问题描述
这是我的问题的说明：
- 我在想开始从左边并添加一个字母，如果是的话，然后检查剩下的，如果可以分离到的话（调用递归函数）。如果是的话，我还导致如果没有的话我会再加上一个字母来第一个字等。但是，这将需要第一个较小的话，我想它的需要开始与算法，首先检查较长的单词，然后小。
- 所以，我在想下手整个单词，然后递归地检查左侧没有最后一个字母，然后右侧部分。如果它不会返回true，然后我搬到留下了光标，然后检查左侧部分无2最后一个字母，右部分（从2最后一个字母）等。但我认为这将需要更多的时间，然后为O（n ^ 2）。
所以，有人可以帮我基本algoritm这将工作，满足时间复杂度？谢谢
So can someone help me with basic algoritm which would work and satisfy time complexity? Thanks
推荐答案
动态规划方法可以基于以下递推公式：
The dynamic programming approach could be based on the following recursive formula:
f(n) = true
f(i) = OR { d(s[i]s[i+1]...s[j-1]) AND f(j) | for each j such that i < j <= n }
从步骤f开始（0）。
Start from f(0).
说明：
如果你到了字符串的结尾 - 你是好（基节）。
否则，试图分裂这个词的地方，你可以从给定的开始（即我），并递归调用的字符串的后缀。
Explanation:
If you got to the end of the string - you're good (base clause).
Otherwise, try to split the word wherever you can from the given start (which is i), and recursively invoke on the suffix of the string.
复杂其实就是为O（n ^ 2 * G（N）），其中 G（N）是它需要为字典检查，如果字是在里面。 （每一个解决方案，需要依赖于它在某种程度上...）
Complexity is actually O(n^2 * g(n)) where g(n) is the time it takes for dict to check if the word is in it. (Every solution need to depend on it somehow...)
转换为DP解决方案：
从后到前填写表格，根据在递推公式描述的逻辑。
Fill the table from last to first, according to the logic described in the recursive formula.
这篇关于动态规划 - 算法修文，其中的所有标点符号缺失的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
