标签: dynamic-programming

几年前,我通过动态编程解决了一个问题:

https://www.thanassis.space/fillupDVD.html

解决方案是用Python编写的.

作为拓展视野的一部分,我最近开始学习OCaml/F#.有什么更好的方法来测试水域,而不是直接将我用Python编写的命令式代码移植到F# - 并从那里开始,逐步向功能性编程解决方案迈进.

第一个直接端口的结果令人不安:

在Python下:

  bash$ time python fitToSize.py
  ....
  real    0m1.482s
  user    0m1.413s
  sys     0m0.067s

在FSharp下:

  bash$ time mono ./fitToSize.exe
  ....
  real    0m2.235s
  user    0m2.427s
  sys     0m0.063s

(如果您注意到上面的"mono":我在Windows下测试过,使用Visual Studio - 速度相同).

至少可以说,我......感到困惑.Python比F#运行代码更快？使用.NET运行时编译的二进制文件运行SLOWER而不是Python的解释代码？!？!

我知道VM的启动成本(在这种情况下为单声道)以及JIT如何改进Python等语言的东西,但仍然......我期望加速,而不是减速!

我也做错了吗？

我在这里上传了代码:

https://www.thanassis.space/fsharp.slower.than.python.tar.gz

请注意,F#代码或多或少是Python代码的直接逐行转换.

PS当然还有其他的好处,例如F#提供的静态类型安全性 - 但如果在F#下强制算法的结果速度更差......至少可以说,我很失望.

编辑:根据评论中的要求直接访问:

Python代码:https: //gist.github.com/950697

FSharp代码:https: //gist.github.com/950699

给定一个排序的数字列表,我想找到最长的子序列,其中连续元素之间的差异在几何上增加.所以,如果列表是

 1, 2, 3, 4, 7, 15, 27, 30, 31, 81

那么子序列就是1, 3, 7, 15, 31.或者考虑1, 2, 5, 6, 11, 15, 23, 41, 47哪个具有5, 11, 23, 47a = 3且k = 2的子序列.

这可以在O(n ²)时间内解决吗？其中n是列表的长度.

我感兴趣的是差异的进展是ak,ak ²,ak ³等的一般情况,其中a和k都是整数,并且在a  = 1 的特殊情况下,差异的进展是k,k ²,k ³等

这是另一个问题,询问如何找到字符串的不同子序列的数量？

例如,

输入
AAA
ABCDEFG
CODECRAFT

输出
4
128
496

我怎么解决这个问题 ？

我收到了这个面试问题,并坚持下去:

从0号站开始有无数的火车站.

有无数的火车.第n列火车在所有k*2 ^(n-1)站停靠,其中k在0和无穷大之间.

当n = 1时,第一列火车停在0,1,2,3,4,5,6等站点.

当n = 2时,第二列火车在0,2,4,6,8等站停止.

当n = 3时,第三列火车在0,4,8,12等站停靠.

给定起始站号和终端站号,返回它们之间的最小停靠点数.您可以使用任何列车从一站到另一站.

例如,start = 1和end = 4之间的最小停靠次数为3,因为我们可以从1到2到4.

我正在考虑一个动态编程解决方案,它将存储在和dp[start][end]之间的最小步数.我们使用构建数组.但我无法让它发挥作用.你是如何解决这个问题的？startendstart...mid1, mid1...mid2, mid2...mid3, ..., midn...end

澄清:

1. 火车只能从较低的号码站向前移动到较高的号码站.
2. 火车可以从停靠的任何车站开始.
3. 可以按任何顺序登上火车.n = 1列车可以在登上n = 3列车之前或之后登上.
4. 火车可多次登船.例如,允许登上n = 1列车,然后登上n = 2列车,最后再次登上n = 1列车.

这是来自Algorithms book(Vazirani)的问题(6.7 ch6),与发现最长回文的经典问题略有不同.我怎么解决这个问题 ？

如果从左到右或从右到左读取它是相同的,则子序列是回文.例如,序列

A,C,G,T,G,T,C,A,A,A,A,T,C,G

Run Code Online (Sandbox Code Playgroud)

有许多回文子序列,包括A,C,G,C,A和A,A,A,A (另一方面,子序列 A,C,T不是回文).设计一个算法,该算法采用一个序列x[1 ...n]并返回(最长的)最长的回文子序列.它的运行时间应该是O(n^2)

我在面试创业公司时被问到这个问题,并在最近的比赛中再次看到了这个问题

Code Sprint:系统

**问题:

您将获得一组天的股票价格.每天,您可以购买一个单位的股票,出售已经购买的任何数量的股票单位,或者什么也不做.通过最佳规划您的交易策略可以获得的最大利润是多少？**

示例(输入即天数可以变化)

5 3 2 =>利润= 0 //由于价格每天都在下降,我们可以赚取的最大利润= 0

1 2 100 =>利润= 197

1 3 1 2 =>利润= 3 //我们以1卖出3买入,然后我们买入1卖出2 ...总利润= 3

我的解决方案

a)找到股票价格最大的那一天.继续购买1单位库存直至当天.

b)如果那天是最后一天,那么退出:

否则:在当天卖出所有股票并在那天之后拆分数组并递减剩余的元素
c)合并利润

例如1 4 1 2 3
a)第2天的最高股票价格..因此我们在第1天购买股票并在第2天卖出(利润= 3)然后我们在剩余的日子里递减:1 2 3

b)最高价格为3(第5天),因此我们在第3天和第4天继续购买股票并在第5天卖出(利润=(3*2 - 3 = 3)

c)总利润= 3 + 3 = 6

这种复杂性证明是O(n ^ 2).这个解决方案通过了11个案例中的10个但超过了最后一个测试案例的时间限制(即最大的输入)

所以我的问题是,任何人都可以想到一个更有效的解决方案吗？有动态编程解决方案吗？

PS:这是我第一次在这里提问.所以如果我需要改进/添加这个问题,请告诉我

在我使用的算法设计和分析导论中,动态编程据说着重于优化原理,"优化问题的任何实例的最优解决方案都由其子实例的最优解决方案组成".

然而,贪婪技术专注于扩展部分构建的解决方案,直到您找到完整问题的解决方案.然后说,它必须是"在该步骤中所有可行选择中最好的本地选择".

既然两者都涉及局部最优性,那么它不是另一个的子集吗？

我正在努力理解线性分区问题的动态编程解决方案.我正在阅读算法设计手册,问题在8.5节中描述.我已经无数次阅读了这个部分,但我只是没有得到它.我认为这是一个糟糕的解释(我现在读到的内容已经好多了),但是我还没有能够很好地理解这个问题以寻找替代解释.欢迎链接到更好的解释!

我找到了一个页面,其中包含类似于本书的文本(可能来自本书的第一版):分区问题.

第一个问题:在本书的示例中,分区从最小到最大排序.这只是巧合吗？从我可以看出,元素的排序对算法并不重要.

这是我对递归的理解:

让我们使用以下序列并将其分为4:

{S1...Sn} =  100   150   200   250   300   350   400   450   500
k = 4

第二个问题:这就是我认为递归将如何开始 - 我理解正确吗？

第一次递归是:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
100   150   200   250   300 | 350 | …

我发现这个挑战问题说明如下:

假设XY平面上有n个矩形.编写一个程序来计算可以与在该平面上绘制的单条直线交叉的最大可能矩形数.

我一直在集思广益,但找不到任何解决方案.也许在某个阶段,我们使用动态编程步骤,但无法弄清楚如何开始.

我在很多地方发现了这个着名的dp问题,但我无法弄清楚如何解决.

您将获得一组n种类型的矩形3-D盒子,其中第i个盒子具有高度h(i),宽度w(i)和深度d(i)(所有实数).你想要创建一个尽可能高的盒子堆叠,但如果下盒子的2-D底座的尺寸都严格大于2的盒子,你只能在另一个盒子的顶部堆叠一个盒子.高架子的D基座.当然,您可以旋转一个框,以便任何一侧作为其基础.也允许使用相同类型的盒子的多个实例.

这个问题对我来说似乎太复杂了.因为它是3D,我得到三个高度,宽度和深度序列.但是因为有可能交换3维,问题对我来说变得更加复杂.所以请有人解释在没有交换时解决问题的步骤,然后在交换时如何解决问题.我对这个问题感到厌倦.所以,请有人解释解决方案的简单方法.