标签: dynamic-programming

我对使用动态编程实现8-queen问题的想法很困惑.似乎DP的一端不可能"如果问题被分解为一系列子问题并且找到了每个子问题的最优解,那么所得到的解决方案将通过这些子问题的解决方案来实现.没有这种结构的动态编程无法解决"(参考).考虑到这一点,7x7电路板的最佳解决方案可能也不是8x8的最佳解决方案(甚至不正确).因此,问题的结果可能无法通过子问题的最优解来实现.

另一方面,DP是回溯问题的优化......如果是这样的话,那么8-queen问题可以通过回溯来解决...这是否意味着只存储死角可以将回溯解决方案转换为DP？如果是这样,则2,1对于父1,1可能不可行,但对于1,2可能是可行的.

更新

任何人都知道使用动态编程是否可以解决8-queen或n-queen问题？如果是,那么您对上述观察的评论是什么？

没有找到任何类似的问题.这是最后一轮Facebook问题:

给你一盒盒子.每个盒子上都有一个非负数,可以重复.

编写一个函数/算法,告诉您选择框的顺序,它将为您提供最大总和.

如果您选择一个方框,它就会从环中取出,它旁边的两个方框(在您选择的方框的右侧和左侧)也是如此.

所以,如果我有一个
{10 3 8 12} 的戒指

如果我选择12,8和10将被销毁而你剩下3.

最大值将首先选择8然后选择10,或者先选择10然后选择8.

我尝试通过取自​​己的值重新分配它们的值,然后减去旁边的两个作为成本.

所以老戒指是{10 3 8 12}

新环是{-5,-15,-7,-6},我会选择最高的.

但是,如果你有{10,19,10,0},这肯定不起作用,你应该取两个10,但算法将取19和0.

请帮忙？

它很可能是动态编程,但我不知道如何.

戒指可以是任何尺寸.

这是问题描述:

假设我们想知道N层建筑中的哪些故事可以安全地从中掉落鸡蛋,哪些会导致鸡蛋在着陆时破裂.我们做了一些假设:可以再次使用在摔倒后存活的鸡蛋.

• 必须丢弃破蛋.
• 所有鸡蛋的跌倒效果都是一样的.
• 如果鸡蛋在掉落时断裂,那么如果从较高的窗口掉落则会破裂.
• 如果一个鸡蛋在摔倒后存活,那么它会在较短的摔倒后存活.
• 不排除一楼的窗户打破鸡蛋,也不排除N楼的窗户不会导致鸡蛋破裂.

给定一个N层建筑和一个鸡蛋供应,找到最小化(在最坏的情况下)确定断裂所需的实验滴数的策略.

我已经看到并解决了2个鸡蛋的问题,其中答案是14 = N = 100.我尝试使用DP了解wiki的通用解决方案,但无法理解他们想要做什么.请告诉他们他们是如何到达DP以及它是如何工作的？

编辑:

本条中给出的最高流量可用d滴和e蛋测试的复发如下:

f[d,e] = f[d-1,e] + f[d-1,e-1] + 1

复发很好,但我无法理解它是如何衍生出来的？

这个解释对我来说并不清楚....我只是希望有人用更清晰的话语向我解释这种情况.

在n个字符的序列S中; 每个字符可能在序列中出现多次.你想找到S的最长子序列,其中所有出现的相同字符都在一个地方;

对于前者 如果S = aaaccaaaccbccbbbab,那么最长的这样的子序列(答案)是aaaaaaccccbbbb ie = aaa__aaacc_ccbbbb.

换句话说,S中出现的任何字母字符可能只出现在子序列中的一个连续块中.如果可能,给出一个多项式时间算法来确定解.

我读过这些话:

为了使动态编程适用,问题必须具有两个关键属性:最佳子结构和重叠子问题.如果通过将最优解与非重叠子问题相结合可以解决问题,则该策略称为"分而治之".这就是mergesort和quicksort未被归类为动态编程问题的原因.

我有3个问题:

1. 为什么mergesort和quicksort不是动态编程？我认为mergesort也可以分为小问题和小问题然后做同样的事情等等.
2. Dijkstra算法是使用动态算法吗？
3. 是否有使用动态编程的应用示例？

假设你是一个小偷,你入侵了一所房子.你在里面找到了以下物品:

一个重3磅的花瓶,价值50美元.
一块重6磅的银块,价值30美元.
一幅重4磅,价值40美元的画作.
重量为5磅,价值10美元的镜子.

这个尺寸为10磅的背包问题的解决方案是90美元.

由动态编程制成的表格是: -

现在我想知道我使用这张表放入麻袋的哪些元素然后如何回溯？

我们有这种算法在O(n)时间内找到给定序列中的最大正子序列.任何人都可以提出类似的算法来找到最小的正连续子序列.

例如,如果给定的序列是1,2,3,4,5,答案应该是1. [5,-4,3,5,4] - > 1是元素[5,-4]的最小正和.

我在查找动态编程问题时发现了这一点.您将获得V0 O0 V1 O1 .... Vn-1形式的无限制表达式

我们必须将括号放在最大化整个表达式值的位置.

V是操作数,O是操作符.在问题的第一个版本中,运算符可以是*和+,操作数是正数.问题的第二个版本是完全一般的.

对于第一个版本,我提出了DP解决方案.

解决方案 - A [] =操作数数组B [] - 运算符数组T(A [i,j]) - 表达式T的最大值(A [0,n-1])=最大值i {(T [A [ 0,i])Oi T(A [i + 1,n-1]))}

边界情况是微不足道的(当i = j时).我需要以下帮助 - 分析此算法的运行时间.如果存在更好的一个.

我正在重新阅读Skiena的算法设计手册,以了解自学校以来我忘记的一些东西,我对他对动态编程的描述感到有点困惑.我看着它在维基百科和其他各种网站,并同时说明一切意义,我无法找出具体的问题我自己.目前,我正在从Skiena的书中解决问题3-5.(给定一个n个实数的数组,找到输入的任何连续子向量中的最大总和.)我有一个O(n ^ 2)解决方案,如本答案中所述.但我坚持使用动态编程的O(N)解决方案.我不清楚复发关系应该是什么.

我看到子序列形成一组总和,如下所示:

S = {a,b,c,d}

a    a+b    a+b+c    a+b+c+d
     b      b+c      b+c+d
            c        c+d
                     d

我没有得到的是如何选择哪一个在线性时间内最大.到目前为止,我已经尝试过跟踪最大值的事情,如果当前值为正,则将其添加到总和中.但是当你有更大的序列时,这就成了问题,因为可能有一些负数会减少总和,但是后来的大正数可能会使它恢复到最大值.

我还想起了总面积表.你可以只使用累积和来计算所有的总和:a,a + b,a + b + c,a + b + c + d等等(例如,如果你需要b + c,它只是(a +) b + c) - (a).)但是没有看到O(N)方法来获得它.

任何人都可以向我解释一下这个特定问题的O(N)动态编程解决方案是什么吗？我觉得我几乎得到它,但我错过了一些东西.

我一直在研究本书中的以下问题.

某种字符串处理语言提供了一种原始操作,它将字符串分成两部分.由于此操作涉及复制原始字符串,因此无论剪切的位置如何,对于长度为n的字符串,都需要n个时间单位.现在假设您要将字符串分成许多部分.中断的顺序可能会影响总运行时间.例如,如果你想在3号和10号位置剪切一个20个字符的字符串,那么在第3个位置进行第一次剪切会产生20 + 17 = 37的总成本,而在第10个位置进行第一次剪切会产生更好的成本20+ 10 = 30.

我需要一个动态编程算法,给出m个切割,找到将字符串切割成m + 1个片段的最低成本.