标签: dynamic-programming

考虑2个序列X [1..m]和Y [1..n].记忆算法将在时间O(m*n)内计算LCS.有没有更好的算法来找出LCS时间？我想对角完成的memoization可以给我们O(min(m,n))时间复杂度.

这是问题所在

ACM国际大学生程序设计竞赛亚洲区域竞赛,横滨,2006-11-05

从x开始并重复乘以x,我们可以计算x^3130次乘法:

x^2 = x * x, x^3 = x^2 * x, x^6 = x^3 * x^3, x^7 = x^6 *x, x^14 = x^7 * x^7 ,
x^15 = x^14 * x, x^30 = x^15 * x^15 , x^31 = x^30 * x

编写一个程序来查找操作次数最少的计算x^n 通过乘法和除法与开始x对给定的正整数n和n<=200

对于n = 31,最少#operations为6,
对于n = 50,最少#operations为7

欢迎任何想法.

这是Vazirani的算法书中的一个问题

该问题的输入是树T,边缘上具有整数权重.权重可以是负数,零或正数.给出线性时间算法以找到T中最短的简单路径.路径的长度是路径中边缘权重的总和.如果没有重复顶点,则路径很简单.请注意,路径的端点不受约束.

提示:这与在树中查找最大独立集的问题非常相似.

如何在线性时间内解决这个问题？

这是我的算法,但我想知道它是否是线性时间,因为它与深度优先没什么不同:

1. 遍历树(深度优先)
2. 保留索引(节点)
3. 添加值
4. 做(1)直到树的尽头
5. 比较总和并打印路径和总和

这个问题与此主题类似,但没有确定的答案.

可能重复:
计算将一个排列转换为另一个排列所需的交换

我正在寻找一种计算某种字符串距离的算法,其中只允许操作是两个相邻字符的转置.例如:
string1:"mother"
string2:"moterh"
距离:2(首先交换"h"与"e"并获得"motehr"然后"h"与"r"导致"moterh")
我知道Damerau -Levenshtein距离这个问题非常相似,但它需要大量的内存(我希望它可以在高达1 000 000个字符的单词上工作得非常快).我已经写过:

int amo = 0;

for (int i = 0; i < n; i++)
{
    if (fromString[i] == toString[i])
        continue;
    char toWhat = toString[i];
    int where = -1;
    for (int j = i; j < n; j++)
    {
        if (fromString[j] == toWhat)
        {
            where = j;
            break;
        }
    }
    while (where != i)
    {
        char temp = fromString[where];
        fromString[where] = fromString[where - 1];
        fromString[where - 1] = temp;
        where--;
        amo++;
    } …

这个包有一些函数可以将递归函数转换为动态编程递归函数,以获得更好的性能:

http://hackage.haskell.org/packages/archive/data-memocombinators/0.3/doc/html/Data-MemoCombinators.html#t:Memo

不幸的是,它们只有最简单类型函数的示例,并且没有关于如何使用2个变量函数的示例.我在哪里可以找到如何将[Int] -> Int -> Int功能转换为动态编程功能的示例？文档说memo2需要两个Memos作为第一个参数,但我不确定这意味着什么.

解:

正如Hammar所描述的那样,而不是将函数定义为:

foo :: [Int] -> Int -> Int
foo list value = ...

使用memo2:

import qualified Data.MemoCombinators as Memo

foo = Memo.memo2 (Memo.list Memo.integral) Memo.integral foo'
  where ... (define foo' with recursive calls to foo.)

在我发现的每个示例中，使用动态编程针对1/0背包问题进行了动态编程，其中项目具有权重（成本）和利润，它从未明确表示要对项目列表进行排序，但是在所有示例中，它们都通过增加两个值来进行排序权重和利润（示例中权重越高，利润越高）。所以我的问题是，当从项目数组/列表中将项目添加到矩阵中时，我可以按任何顺序添加它们，还是添加权重或利润最小的项目？因为从多个示例中我发现我不确定这是否只是一个巧合，否则您实际上每次确实需要将最小的权重/利润放入矩阵中

以下是某人给我的练习面试问题,我不确定最佳解决方案是什么:

给定一组范围:
(例如S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)},并给予目标范围R(例如R = (3, 13)-这意味着会从3到13的范围内)写一个算法来找到最小的范围集合覆盖你的目标范围内的所有在该范围内的. set必须重叠才能被视为跨越整个目标范围.(在这个例子中,答案是{(3, 9), (9, 12), (11, 14)}.

解决这个问题的最佳方法是什么？我以为这将使用贪婪算法完成.在上面的示例中,我们将查找与3相交的所有数字,并从具有最高max的数字中选择.然后我们会用我们刚刚选择的那个做同样的事情.所以,既然我们选择了(3,9),我们现在想要找到所有与9相交的范围,其中我们选择具有最高最大值的范围.在那次迭代中,我们选择了(9,12).我们对那个做同样的事情,我们发现与12相交的下一个范围,最高的最大值是(11,14).

在那次迭代之后,我们看到14大于13(我们的范围的最大值),所以我们可以停下来.

我对这个算法的问题是,如何有效地查询相交的范围？如果我们尝试线性搜索,我们最终会得到一个算法O(n^2).我的下一个想法是每次运行循环时从我们的列表中删除任何相交的范围.所以在第一次迭代中,我们交叉(1,4)和(3,9).在我们的下一次迭代中,我们交叉(9,12),(3,9)和(8,10).所以在最后一次迭代中,我们所要看的只有{(30,40),(20,91),(6,7)}.我们可以通过删除min> 13和max <3的所有内容来提高效率.问题是这仍然可能还不够.在我们的范围范围内存在大量重复序列的潜在问题.如果我们的范围列表中包含类似{(6,7),(6,7),(6,7),(6,7),(6,7)},我们将不得不通过这些每次都看,甚至虽然它们对我们没用.即使我们只存储唯一值(通过把它们放在一个集),我们可能有一个非常大的范围内,有一堆,这是我们的目标范围内的范围,但我们也有一个范围内,跨越几乎整个目标范围.

什么是查询我们的范围的有效方法？或者可能,解决这个问题的更有效算法是什么？

虽然标准的背包问题可以通过动态编程来解决,但我试图稍微扭转问题以清除我的概念,但是我发现它可能比我想象的更难.

原始的背包问题是,给定一个带有尺寸的背包W,以及一个重量w[i]和有一个值的物品清单v[i],找到能够适合具有最高总价值的背包的物品子集.

据我所知,这可以通过O(Wn)动态编程来完成,其中n是项目数.

现在,如果我尝试添加m约束,它们中的每一个都是一对只能相互挑选的项目(即如果存在项目A和项目B的约束,那么我只能选择其中一个而不是两个)

在这样的约束下,这个问题仍然可以通过动态编程解决O(Wn)吗？

最近我设计了一个儿童难题来解决.但是,我想现在最优解决方案.

问题如下:你有这个数字由小方块组成

你必须用更大的方块填充它,并使用下表进行评分:

| Square Size | 1x1 | 2x2 | 3x3 | 4x4 | 5x5 | 6x6 | 7x7 | 8x8 |
|-------------|-----|-----|-----|-----|-----|-----|-----|-----|
| Points      | 0   | 4   | 10  | 20  | 35  | 60  | 84  | 120 |

有很多可能的解决方案来检查它们.其他人建议动态编程,但我不知道如何将数字划分为较小的数字,这些数字放在一起具有相同的最优解.

我想找到一种方法,在合理的时间内找到解决这类问题的最佳方案(比如常规桌面上最多几天).到目前为止,使用猜测算法和一些手动工作找到的最高分是1112.

还可以理解组合子问题的类似问题的解决方案.我不需要写出所有代码.算法的概要或想法就足够了.

注意:可以容纳的最大正方形是8x8,因此不包括较大正方形的分数.

[[1,1,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1],
 [1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1],
 [1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1],
 [0,0,0,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
 [0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1],
 [0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1],
 [1,0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1],
 [1,1,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1],
 [1,1,1,0,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,0,0],
 [0,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,1,0,0,0],
 [0,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
 [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0],
 [0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1],
 [0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1],
 [0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],
 [0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0],
 [0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0],
 [0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
 [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
 [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
 [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1],
 [0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1],
 [0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1], …

给定一个正整数数组。如何找到L具有max和的长度的子序列，该子序列的两个相邻元素之间的距离不超过K

我有以下解决方案，但不知道如何考虑长度L。

1 <= N <= 100000，1 <= L <= 200，1 <= K <= N

f [i]包含以i结尾的子序列的最大和。

for i in range(K, N)
    f[i] = INT_MIN
    for j in range(1, K+1)
        f[i] = max(f[i], f[i-j] + a[i])
return max(f)