投身烈火
Keep Walking

聊聊动态规划(1) -- 概念

之前某天面试了个年轻的工程师,习惯性的问了几个简单的算法题,冒泡排序二分查找之类的。他没有答上来,解释道这些平时开发中根本不会用到,就算需要,各种开源框架也都封装的烂大街了,根本不用自己写。

听他这么说着,仿佛看到了几年前的自己。当时我也觉得不用了解算法知识,知道冒泡快排能应付面试就得了。前端面向的是界面及交互实现,除非你填游戏或者富文本的坑,不然哪儿用的上什么算法。真需要了,上网搜呗。Max Howell 连个翻转二叉树都不会,不也照样把 Homebrew 做出来了吗。

直到我听了一次之前的领导的分享。他在分享中介绍,面试中考察算法知识,并不是想看你背了多少题,而是想考察你解决复杂问题的能力。算法能力体现的不只是知识储备,还能体现一个人的聪明才智。

听完之后我茅厕顿开。我的理解是,所谓的算法,其实就是你解决问题的方法。所以就算你不知道最佳答案,用你知道的知识解决问题,也算是一种算法。比如你要去个地方,可以坐公交坐地铁,你都不知道怎么坐,走过去也算是一种算法。算法题也并不是跟实际开发没有关联。就好比 “水池能装100L水,进水管每分钟进水10L,出水管每分钟出水5L,多长时间水池能满?” 这种傻逼的问题,如果改成 “一个驴牌的包包1万,你一个月挣5000,花2000,多长时间能买的起?” 不就有了实际的意义了吗……话说我还真是喜欢打比方的( ̄▽ ̄)……

那么,怎么才算真正具备一定算法能力,入了算法的门儿了呢?显然只会个排序肯定是不行的……当然我并不是说排序算法就简单,各种排序算法优化啥的我觉得也挺难的……我个人觉得,在各种常见的算法中,动态规划应该算是一道坎儿,过去了就算入门儿了。winter大神也说过,写出动态规划,再谈算法。

那么动态规划到底是什么呢?

动态规划(dynamic programming)是求解多阶段决策过程(multistep decision process)最优化的数学方法。

第一次听到这个定义的时候我脑子里只有 “说人话” 这三个字……ok,让我们来仔细掰吃掰吃。

仔细观察发现,这个定义可以拆分成以下两部分:

  1. 动态规划用来求解问题的最优化方案的
  2. 问题表现为多阶段决策过程

最优化方案比较好理解。所谓多阶段决策,是将决策问题的全过程恰当地划分为若干个相互联系的子过程(每个子过程为一个阶段),以便按照一定的次序去求解。也就是说,一个大的问题可以被划分为若干个相互联系的子问题。这种相互联系的子问题,又叫交叠子问题。举个例子来说明交叠子问题,以斐波拉契(Fibonacci)数列为例,计算第100项的时候,需要计算第99项和98项;在计算第101项的时候,需要第100项和第99项,这时候你还需要重新计算第99项吗?不需要,你只需要在第一次计算的时候把它记下来就可以了。上述的需要再次计算的“第99项”,就叫交叠子问题。

在理解了上面每个学术名词的概念以后,可以得出一个结论,所谓动态规划,就是对于某一类问题的解决方法……呃……可能会有人觉得这是废话,但其实我们正在一步步接近问题的核心。个人觉得,动态规划的重点就在于如何鉴定“某一类问题”是动态规划可解的,而不是纠结用什么解决方法。因为用什么解决方法,取决于你从什么角度观察问题,拆分子问题。寻找看问题的角度,才是动态规划的核心。

那么,如何鉴定动态规划可解的问题呢?这会是一个 long long story……所以,咱们下期再讲~~( ̄▽ ̄)~~!!!

好的那么由于时间不足本次的博客就到这里,简单预告一下,下期博客会从计算机是怎么工作的说起了……

如果不出意外的话,大概可能maybe也许下周五会更新吧~!能不能准时更新,就全看米娜桑点赞打赏转发安利发评论的热情啦~!

白了个白~!