[0-9]元素序列中的增加子序列数
[0-9]元素序列中的增加子序列数
提问于 2014-06-27 17:03:31
在未知范围值元素序列的情况下，Number of all increasing subsequences in given sequence问题给出了O(n^2)中的一个解。
我听说过O(9*n)中的解，如果序列仅由区间0,9中的元素组成。如果你知道这个算法，请告诉我。
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-06-27 19:06:52
下面是一个算法：
1)让我们调用dp[i] =具有最后一个元素i(0 <= i <= 9)的递增子序列的数目。最初它是用零填充的。
2)现在我们可以通过以下方式迭代序列并计算dp：
让我们假设当前元素是d(0 <= d <= 9)。然后可以像这样更新dp：
for prev = 0...d - 1
dp[d] += dp[prev] //continue one of the previous sequences.
dp[d] += 1 //start a new sequence that consists of only one element.3)在迭代了序列的所有元素之后，
答案仅仅是dp[i]与0 <= i <= 9之和。
请注意，该算法只有在假设算术操作具有O(1)时间复杂度(可能不是这样，因为增加的子序列数量可能很大)时才有期望的复杂度。
Stack Overflow用户
发布于 2014-06-27 19:23:13
改变问题中所涉及的算法，我相信这也将满足复杂性要求：
input[i] = input array
n = size of input
dp[i] = number of increasing subsequences with i as the last element (same size as input)
initialize dp[i] = 0 for all 0 <= i < n
//Every possible input can be appended on to one previously found
// increasing subsequence
for (j = 0; j <= 9; j++) {
//Running total of increasing subsequences that occur earlier in the input using
// smaller numbers than j
int smallerSum = 0;
for (i = 0; i < n; i++) {
//This spot in dp was tallied already, need to add it to the running total
if (input[i] < j) {
smallerSum += dp[i]
//Add 1 to the running total, this should be the final answer for this spot in dp
} else if (input[i] == j) {
dp[i] = smallerSum + 1;
}
}
}
return the sum of all elements of dp通常，嵌套的for-循环是O(n^2)的死赋值，但在这种情况下，我们在一个常量上循环，使它成为O(n)。
在一般情况下，这个算法是O(n*k)，其中n是输入数组的大小，k是可能的输入值的数目。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24457214
复制相关文章
相似问题
腾讯云开发者
