阅读 552

前端面试算法-动态规划

哇,你这个题目怎么和我刚刚看到一篇好像哦,没错,我也看了前端跳槽面试算法——动态规划 我这篇算是那篇的补充版吧,补充了一些我自己的想法。

首先看一下题目(复制自前端跳槽面试算法——动态规划):

有一个只能容纳10本书的单层书架,你每次只能放1本或2本书。要求用程序求出你将书架填满一共有多少种方法。

比如,每次放1本书,一共放10次,这是其中一种方法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。

再比如,每次放2本书,一共放5次,这是另一种方法。我们可以简写成 2,2,2,2,2。

这里我更愿意把他抽象成数学题目,即用数字1和数字2组合成一个一维数组,并且和为10,问有多少种不同的组合方式。

这里我认为【最优子结构】是比较难想的,即F(10)代表和为10的组合方案数,F(9)代表和为9的组合方案数,我也是看到了他的解析才想到(作为一个学过ACM的人,感觉自己好菜啊)这之后便能想到F(10) = F(9) + F(8)

其实这里还能扩展更多,比如:单层书架可以放100本书,你可以选择放2本,4本和6本,请问有多少种组合?其实这类就都应该会了,显然它的状态转移方程是F(n) = F(n-2) + F(n-4) + F(n-6) 最后算出F(100)即可。

其实这个我相信大家都学过,因为这就是斐波那契数列的一种变式,而第一个问题就和斐波那契数列一模一样了有木有,都是F(n)=F(n-1)+F(n-2)

再比如:一个楼梯共有50层台阶,你可以选择跨1层,跨2层,跨3层的方式通过楼梯,请问通过楼梯共有多少种方案?这个把用数学把问题抽象出来,就和上面是一毛一样的,就留给大家去思考了。

最后我还想讨论一下LeetCode 63题的代码,题目在前端跳槽面试算法——动态规划这里,我就不复制了,它是用递归来写的,递归会很慢,而且它的时间复杂度也不好计算(好吧,是我不会),其实没有必要,可以使用二维数组来模拟,这里是代码 如下图便是结果,时间复杂度是O(m*n),可以超过98%的用户。