标签: dynamic-programming

"观察当你从杂志中剪切一个角色时,页面背面的角色也会被移除.给出一个算法来确定你是否可以通过粘贴来自给定杂志的剪切来生成给定的字符串.假设你是给定一个函数,该函数将识别字符及其在页面反面的位置,用于任何给定的字符位置."

我该怎么做？

我可以做一些初步的修剪,这样如果一个需要的角色只有一种方法可以被拾取,那么它最初是在转动动态技术的子问题之前采取的,但是在这个初始修剪之后呢？

什么是时间和空间的复杂性？

我已经在某些文本中看到了关于算法分析和设计的剪切和粘贴样张的参考.在为优化问题证明最优子结构时,通常会在动态规划的上下文中提及它(参见第15.3章CLRS).它还显示了图形操作.

这种证明的主要思想是什么？我如何使用它们来证明算法的正确性或特定方法的便利性？

建筑桥梁问题陈述如下:

有一条河流水平穿过一个区域.河流上下都有一组城市.河上的每个城市都与河下的城市相匹配,您可以将这种匹配作为一组配对.

您有兴趣在河对岸建造一组桥梁,以连接最大数量的匹配城市,但您必须以两座桥梁彼此不相交的方式进行连接.

设计算法以尽可能有效地解决此问题.

我听说这个问题与最长的子序列问题有关,但我不知道如何在这里使用它.例如,如果我们给对了

2  5  8  10
6  4  1  2

那么我们为LIS考虑哪个序列？

谢谢!

我正在研究函数式语言,我发现一些算法(特别是那些使用动态编程的算法)更难编写,有时在最坏的情况下运行时效率更低.是否有一类算法在具有不可变变量和副作用的函数式语言中效率较低？

是否有人可以指向我的参考,这将有助于编写更难编写的算法(可能是那些通过共享状态优化的算法)？

谢谢

给定一个图像和一组标签附加到图像上的特定点,我正在寻找一种算法,以一定的约束将标签布局到图像的两侧(每侧标签大致相同,标签大致等距离,将标签连接到各自的点,没有线交叉的线.

现在,通过按Y坐标(它们所指的点)对标签进行排序,通常可以非常天真地找到近似解决方案,如本例所示(仅限概念证明,请忽略实际数据的准确度等)!

现在为了满足没有过境的条件,我想到了一些想法:

• 使用遗传算法找到没有交叉的标签的排序;
• 使用另一种方法(例如动态编程算法)来搜索这样的排序;
• 使用上述算法之一,允许间距和排序的变化,找到最小化交叉数和从均匀间距变化的解决方案;
• 也许有一些标准我可以用来在某些标准内粗略搜索标签的每个可能的排序(如果它们的距离大于X,不要重新排序两个标签);
• 如果所有其他方法都失败了,只需尝试数百万的随机排序/间距偏移,并选择一个给出最小交叉/间距变化的偏移量.(优点:直接进行编程,可能会找到一个足够好的解决方案;虽然不是一个显示停止的轻微劣势:也许不能在应用程序中动态运行它,以允许用户更改图像的布局/大小. )

在我开始其中之一之前,我会欢迎其他人的意见:有其他人遇到过类似问题并有任何信息来报告上述任何方法的成功/失败,或者他们是否有更好的/更简单的解决方案,我没有发生？感谢您的输入!

给定长度为N的字符串S，返回一个字符串，该字符串是将'?'字符串S中的每个字符替换为一个'a'或一个'b'字符的结果，并且不包含三个相同的连续字母（换句话说，处理后的字符串中'aaa'不可能'bbb'出现这两个字母）。

例子：

Given S="a?bb", output= "aabb"

Given S="??abb", output= "ababb" or "bbabb" or "baabb"

Given S="a?b?aa", output= "aabbaa"

1<=n<=500000

我使用回溯解决了这个问题，但是我的解决方案很慢并且不适用于更大的 N 值，有更好的方法吗？

给定任意数n和n上的三个运算:

1. 加1
2. 减去1
3. 如果数字是偶数则除以2

我想找到上面的操作的最小数量,以减少n为1.我尝试过动态编程方法,也修复了BFS,但是n可能非常大(10 ^ 300)而且我不知道如何制作我的算法快点.贪婪的方法(如果偶数则除以2,如果是偶数则除1)也不能给出最佳结果.还有其他解决方案吗？

给出如下所示的电话键盘:

1 2 3
4 5 6
7 8 9
  0

从1开始可以形成多少个不同的10位数字？约束是从1位数到下一位数的运动类似于国际象棋游戏中骑士的运动.

例如.如果我们在1那么下一个数字可以是6或8如果我们在6那么下一个数字可以是1,7或0.

允许重复数字 - 1616161616是有效数字.

有多项式时间算法可以解决这个问题吗？问题要求我们只计算10位数字,而不一定列出数字.

编辑:我尝试将其建模为图形,每个数字都有2或3位数作为其邻居.然后我使用DFS导航到10个节点的深度,然后在每次达到10的深度时增加数字的数量.这显然不是多项式时间.假设每个数字只有2个邻居,则需要至少2 ^ 10次迭代.

这里的变量是位数.我采取了例如.10位数字.它也可以是n位数.

我有一些这样的数据:

1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15

我将尝试表示使其更清晰:

        1     2     3     4     5     6     7     8     9     10     11     12     13     14     15
1             |--------------------------------------X---------|
2                   |--------------------------------X--------------------------------------------|
3                         |--------------------------X---|
4                                                  |-X-------------------------------------|
5                                           |--------X------------------------------|
6                               |--------------------X----------|
7                                                                     |---------------------------|

因此,在示例情况下,8-9如果使用第二个方案是关键期,因为所有点都是活动的.在python中解决这个问题的快速而好的方法是什么？我正在考虑使用动态编程,但还有其他建议的方法吗？

我的方法直到现在:

我从实时的角度思考更多.因此,每当我得到一个新的点,我这样做:假设我已经得到了2-10然后我得到3-15了最大的开始和结束的最小值所以这种情况它是3-10并将此间隔的计数增加到2.然后第三点进来4-9接送最大是4和min为9并更新值3-10到4-9时和更新计数到3.现在8-14进来,我选择这个间隔的开始是大于4-9和该间隔的结束小于 …

这是我的一个采访问题,我很尴尬地被它弄得很难过.想知道是否有人能想出答案并为它提供大的O符号.

Question: Given a string of numbers and a number of multiplication operators, 
          what is the highest number one can calculate? You must use all operators

你不能重新排列字符串.您只能使用乘法运算符来计算数字.

例如String = "312",1个乘法运算符

你可以做3*12 = 36或31*2= 62.后者显然是正确的答案.