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

内容简介：聊聊动态规划(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也许下周五会更新吧~！能不能准时更新，就全看米娜桑点赞打赏转发安利发评论的热情啦~！

白了个白~！

以上所述就是小编给大家介绍的《聊聊动态规划(1) -- 概念》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

• 深入浅出聊聊Kubernetes存储（一）：详解Kubernetes存储关键概念
• 简单聊聊视频基本概念以及在信息流内容中心的处理
• 聊聊你可能并没有完全掌握的 Flex 布局：从概念入手，丝丝入扣
• Flume的基本概念
• lucene基础概念
• arcgis 图层概念

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。