动态规划:二项式序列

栏目: 编程工具 · 发布时间: 5年前

内容简介:本文为 AI 研习社编译的技术博客,原标题 :Dynamic Programming — Binomial Sequence

动态规划:二项式序列

本文为 AI 研习社编译的技术博客,原标题 :

Dynamic Programming — Binomial Sequence

作者 |  Barun Halder

翻译 | 孙稚昊2  

校对 | 邓普斯•杰弗        审核 | 酱番梨       整理 | 立鱼王

原文链接:

https://medium.com/@bhalder/dynamic-programming-binomial-sequence-62e92d1cc2b1

今天,我终于理解了帕斯卡三角的实际应用。帕斯卡序列是我在大学第一年编程实现的东西。这是一个很有趣的练习。它是一种找到规律并用C或 Java 编程实现的问题。

动态规划问题可以是非常难的。二项式序列和它的变种问题一直都是我的短板。我从没简单地得到答案,有时即使我有了想法,也不能直接写出可以工作的代码。这是为什么我这次决定尝试一种新的动态规划方法,并且阅读Skiena的前八章。在阅读的过程中,问题被探讨,并且我一下豁然开朗。二项式,帕斯卡三角和动态规划之间的联系被重新建立起来。讽刺的是,我一直困惑的问题,二项式问题的变种的答案,就是我写的第一个程序,帕斯卡三角。

动态规划:二项式序列

帕斯卡三角

帕斯卡三角如上图所示。其中每一个元素都是它正上面两个数字之和。问题就是,什么叫“正上方”?这样的东西要如何在代码中表达?

如果我们用图中的6作为例子,它正上方的两个数字是3和3. 6在第4行,第3列。两个3在上一行--第三行,第二和第三列。同样的规律也适用于第五行的两个10. 现在,我们能够提取的规律是--- 第[n, k] 个元素是 第 [n-1 , k] , [n-1, k-1]个元素的和。

那么,这和二项式原理有什么关系呢?回想一下,二项式数是像这样的:

动态规划:二项式序列

二项式序列

这个的物理意义是:如果我们从n 个元素中选取k  个元素。我们既可以先选择第n 个元素,然后从剩下n- 1个元素中选取 k-1 个,也可以丢掉第n 个元素,从剩下n-1 个元素中选取k 个。我们在帕斯卡三角中看到的对称性在这里很明显。

现在来用代码实现它。如果我们把每个 nCk 的结果存进一个矩阵中,我们可以更高效地计算高维序列。很明显,一个值被计算好后,它会被保存起来给后续的运算使用。这很有记忆化的潜力!

我们先从二项式序列的递归解开始。这里面可以观察到明显的递归关系。对于任何递归函数,初始值都是必须的。对于二项式序列,我们用从n个元素中选取0个元素的情况当作初始值。这样的选择只有一种方法:空集。

另一种初始情况是:从n 个元素集中选取全部的n 个元素,只有一种方法。最后,从n个元素中选取1个,有n种方法。这就是我们需要的所有初始情况。

递归解如下图所示:

动态规划:二项式序列

二项式序列-递归解

注意上面的解法中有很多被重复计算的子问题。为了避免重复计算,我们把中间结果存在一个矩阵中。我们来用一种遍历的方法来实现它。我们先用上文提到的初始情况来填充矩阵。(图中我用了简单的方法,把所有值都初始化为1。这有些浪费)这里只有从n 中取1的情况没被表示。我们要计算得到这种情况。用 python 实现的遍历解法如下图所示: 雷锋网雷锋网雷锋网 (公众号:雷锋网)

动态规划:二项式序列

二项式序列--遍历解

运行的结果如下图所示:

动态规划:二项式序列

输出结果

在这篇文章中,我们讨论了二项式序列和它与帕斯卡三角之间的关系。我们沿着这个关系,并且意识到有时连接一些点要花10年。我们还讨论了同样解的递归和遍历方法。我很推荐阅读Skiena 和 CLRS 来学习你不熟悉的算法。

继续编程!

想要继续查看该篇文章相关链接和参考文献?

点击 动态规划:二项式序列 即可访问:

https://ai.yanxishe.com/page/TextTranslation/1416

社长今日推荐: AI入门、大数据、机器学习免费教程

35本世界顶级原本教程限时开放,这类书单由知名数据科学网站 KDnuggets 的副主编,同时也是资深的数据科学家、深度学习技术爱好者的Matthew Mayo推荐,他在机器学习和数据科学领域具有丰富的科研和从业经验。

点击链接即可获取: https://ai.yanxishe.com/page/resourceDetail/417

雷锋网原创文章,未经授权禁止转载。详情见 转载须知


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

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

Pro Django

Pro Django

Marty Alchin / Apress / 2008-11-24 / USD 49.99

Django is the leading Python web application development framework. Learn how to leverage the Django web framework to its full potential in this advanced tutorial and reference. Endorsed by Django, Pr......一起来看看 《Pro Django》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

html转js在线工具
html转js在线工具

html转js在线工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具