标签: dynamic-programming

什么是动态编程？

它与递归,记忆等有什么不同？

我已经阅读了维基百科上的文章,但我仍然不太了解它.

memoization和动态编程有什么区别？我认为动态编程是memoization的一个子集.这样对吗？

我有一组整数.我想使用动态编程找到该集合中增长最长的子序列.

的自下而上的方法(动态编程)在于第一看"较小"的子问题,进而解决使用所述溶液到较小的问题较大子问题.

在自上而下的在于解决"自然地"的问题,并检查是否已计算出前解决的子问题.

我有点困惑.这两者有什么区别？

想象一下,你在一座有猫的高楼里.这只猫可以在低矮的故事窗口中摔下来,但如果从高楼层抛出,它就会死亡.你怎么能用最少的尝试数来计算猫可以存活的最长时间？

显然,如果你只有一只猫,那么你只能线性搜索.先从一楼扔猫.如果它存活下来,从第二个扔掉它.最终,从地板f抛出后,猫会死.然后你知道楼层f-1是最大的安全楼层.

但是,如果你有一只以上的猫怎么办？您现在可以尝试某种对数搜索.让我们说这个版本有100层,你有两个相同的猫.如果你将第一只猫从50楼扔出去并且死亡,那么你只需要线性搜索50个楼层.如果您为第一次尝试选择较低楼层,则可以做得更好.假设您选择一次解决20个楼层的问题,并且第一个致命楼层是#50.在这种情况下,你的第一只猫将在从60楼死亡之前从20楼和40楼的飞行中幸存下来.你只需要分别检查楼层41到49.这总共有12次尝试,这比你试图使用二进制消除所需的50次要好得多.

一般来说,对于有2只猫的n层建筑来说,最好的策略和最坏情况的复杂性是什么？n楼和m猫怎么样？

假设所有猫都是等同的:它们都将从给定窗口的摔倒中幸存或死亡.此外,每一次尝试都是独立的:如果一只猫在跌倒时幸存下来,它就完全没有受到伤害.

这不是家庭作业,虽然我可能已经解决了一次学校作业.这只是一个异想天开的问题,今天突然出现在我脑海中,我不记得解决方案了.如果有人知道此问题的名称或解决方案算法的加分点.

Divide和Conquer算法和动态规划算法有什么区别？这两个术语有何不同？我不明白他们之间的区别.

请举一个简单的例子来解释两者之间的差异以及它们看起来相似的基础.

我正在为想要学习动态编程的人寻找一个易于理解的例子.关于什么是动态编程,这里有很好的答案.斐波那契序列是一个很好的例子,但它太小而不能划伤表面.它看起来是一个很好的主题,虽然我尚未参加算法课程,但希望它在我的春季名单上.

有一个大小为N x M的网格.一些细胞是由'0'表示的岛,而其他细胞是水.每个水电池上都有一个数字,表示在该电池上制造的电桥的成本.您必须找到所有岛屿可以连接的最低成本.如果单元共享边或顶点,则单元连接到另一个单元.

可以用什么算法来解决这个问题？
编辑:如果N,M的值非常小,可以用作蛮力方法,比如说NxM <= 100？

示例:在给定图像中,绿色单元格表示岛屿,蓝色单元格表示水,浅蓝色单元格表示应在其上制作桥梁的单元格.因此,对于下面的图像,答案将是17.

最初我想到将所有岛屿标记为节点并用最短的桥连接每对岛屿.然后问题可以减少到最小生成树,但在这种方法中我错过了边缘重叠的情况.例如,在下图中,任意两个岛之间的最短距离为7(标记为黄色),因此通过使用最小生成树,答案为14,但答案应为11(以浅蓝色标记).

我知道这Knapsack是NP完全的,而DP可以解决.他们说DP解决方案是pseudo-polynomial,因为它在"输入长度"(即编码输入所需的位数)中是指数的.不幸的是我没有得到它.有人能pseudo-polynomial慢慢向我解释那件事吗？

输入:二维数组NxN - 矩阵 - 具有正负元素.

输出:任何大小的子矩阵,使得其总和是所有可能子矩阵中的最大值.

要求:算法复杂度为O(N ^ 3)

历史:在Algorithmist,Larry和Kadane算法的修改的帮助下,我设法解决了部分问题,即仅在Java中确定求和.
感谢Ernesto设法解决问题的其余部分,即确定矩阵的边界,即左上角,右下角 - 在Ruby下面.