我正在解决一个程序设计的挑战,在一个2D NxN矩阵中寻找最长的递增子序列的长度。在序列的每个元素中,行和列都必须增加(不需要连续)。本文用动态规划方法求解,但它是O(n^4),效率低。然而,在O(n^3)中有许多解。一种这样的解决办法是:
scanf("%d", &N);
for(i = 1; i <= N; i++) {
for(j = 1; j <= N; j++) {
scanf("%d", &L[i][j]);
}
}
Answer = 0;
memset(maxLength,0,sizeof(maxLength));
for (i=1;i<=N;i++)
{
maxLength[1][i] = 1;
maxLength[i][1] = 1;
}
//
for (i=2;i<=N;i++)
{
memset(minValue,0,sizeof(minValue));
curLen = 1;
minValue[1] = L[i-1][1];
for (j=2;j<=N;j++)
{
for (p=1;p<i;p++)
{
tmpLen = maxLength[p][j-1];
if (minValue[tmpLen] == 0)
{
minValue[tmpLen] = L[p][j-1];
curLen = tmpLen;
}
else if (minValue[tmpLen]>L[p][j-1])
{
minValue[tmpLen] = L[p][j-1];
}
}
max = 1;
for (p=curLen;p>0;p--)
{
if (L[i][j]>=minValue[p])
{
max = p+1;
break;
}
}
maxLength[i][j] = max;
Answer = Answer>max?Answer:max;
}
}
// Print the answer to standard output(screen).
printf("%d\n", Answer);
有人能解释一下它的工作原理或其他O(n^3)方法吗?我根本听不懂:(。
在O(n3)时间内解决这个问题并不是那么困难。然而,我没有阅读源代码,所以我不知道下面是不是它做了什么,但这里有一个想法,如何可以这样做。
诀窍在于更新过程。我猜你最初做的是下面这些。
假设您正在考虑橙色矩形中的一个元素。前面的步骤必须源自蓝色矩形(您已经解决了)。这会得到一个正确的答案,但很容易看出它会得到一个(n4)的结果,因为您可以将橙色和蓝色矩形都设为(n2),您需要考虑它们之间的所有对。(这很容易形式化。)
这是(我留给你的)诀窍。如果您在单元格中存储了足够的信息(或者在辅助数据结构中,这并不重要),那么对于您考虑的橙色列中的每个元素,您只需要查看它左边的列(对于橙色行也是如此--您只需要查看它上面的行中的元素)。
因此有O(n)个外部迭代(在每个迭代中,您考虑一行和列)。每个这样的行/列有O(n)个元素,每个左/上行/列有O(n)个元素2。乘法使目标变得复杂。
我在阅读了允许K个异常的最长递增子序列后创建了这个线程。我意识到提问的人并没有真正理解这个问题,因为他指的是一个链接,该链接解决了“允许一次更改的最长递增子数组”问题。所以他得到的答案实际上与李的问题无关。 假设给定一个长度为N的数组A。查找允许K个异常的最长递增子序列。 示例:N=9,K=1 A=[3,9,4,5,8,6,1,3,7] 答案:7 说明: 最长递增子序列为:3,4,5,8(或6),
最长增子序列是我们熟知的问题,我用耐心算法给出了一个解决方案。 我曾想过先用我的算法,然后找到长度为N的第一个序列,但不知道该怎么做。 那么,如何从随机整数序列中找到第一个最长的递增子序列呢? 我的代码段: 我的代码返回:1 2 8 第一个序列是:3 6 8 另一个例子: 我的代码正确返回:1 2 3 基本上,只要第一个最长序列与最佳最长序列相同,我的代码就能工作。但是当你有一堆相同长度的最长序列
我试图在c中实现最长公共子序列算法,矩阵c[]]存储最长公共子序列的长度,行[][]存储c[]]矩阵中的父块行,列[][]存储父块列。 我对解决LCS的方法非常不便和低效表示歉意,但什么都没有打印出来。请帮忙。
对于最长的子序列递增问题,我设想保持一个总是有序的DP数组,将最大值保持在最远端。看起来像这样的东西: 我得出第一个不正确的解决方案的思路是,我们想从第一个元素开始查看整个数组,计算LIS,然后在数组末尾递增地添加一个值。在执行此操作时,我们将DP数组中的LIS增量计算为旧子数组加上我们添加的新元素的LIS。这意味着在数组的索引处存在长度为的子数组的LCS值。 更清楚地说 2.)对原始输入数组进行
在最多一个序列存在重复的情况下,可以将最长公共子序列问题转化为最长递增子序列问题。减少问题的过程说明在这里: 假设您有以下序列: 然后,创建一个整数序列S3,其中您必须将S2的每个元素的位置放在S1中(如果元素在S1中不存在,那么忽略那个元素)。在本例中: 这种方法是如何工作的?为什么这种约简解决了寻找最长公共子序列的问题?
我为最长的递增子序列生成了以下代码: 输入:nums=[10,9,2,5,3,7,101,18] 输出:4 说明:最长的递增子序列是[2,3,7,101],因此长度为4。 有人能帮我理解这句话吗 三个点的意义是什么?正如我们所知,映射生成键值对,映射与切片一起做什么?