動態規劃:二項式序列

2020-12-05 雷鋒網

本文為 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

相關焦點

  • 乾貨總結 | 動態規劃十問十答
    今天給大家總結動態規劃十問十答，快速幫你掃盲動態規劃。答：動態規劃是一種通過「大而化小」的思路解決問題的算法。區別於一些固定形式的算法，如二分法，寬度優先搜索法，動態規劃沒有實際的步驟來規定第一步做什麼第二步做什麼。
  • 二項式的有理項
    牛頓二項式定理:（Binomial theorem）>二項式定理，又稱牛頓二項式定理，由艾薩克·牛頓於1664年-1665年間提出。二項式定理可以推廣到任意實數次冪，即廣義二項式定理。數學小怪獸：除了常數項，二項式還有其他考點嗎？利用二項式定理，我們得到了展開式。
  • 牛頓二項式定理
    牛頓二項式定理:（Binomial theorem）二項式定理，又稱牛頓二項式定理數學小怪獸：學習二項式定理有什麼用？二項式定理，在組合理論、開高次方、高階等差數列求和，以及差分法中有廣泛的應用 。值得一提的是，二項式定理與楊輝三角形是一對天然的數形趣遇。如果說二項式定理屬於計算數學範疇，那麼楊輝三角可以說是把「數形結合」帶進了計算數學。二項式展開式的係數問題，本質上是組合計數問題。
  • 二項式定理
    其中二項式定理就是組合公式的一個簡單應用。二項式是指兩個變量和的正整數次方的展開式，n次展開式的展開項的種類是n+1種，因為展開之後的每項的次數之和都是n次，一共有n+1種兩個變量指數次數的組合。假設求取（a+b）的n次方的展開式，那麼其中a的指數為m的那一項的係數是多少呢？
  • 二項式定理的通俗解釋
    在中學數學裡，我們會經常遇到一個叫做「二項式定理（Binomial Theorem）」的知識。
  • 二項式定理知識點的匯總以及拓展
    二項式定理的公式的由來二項式定理是由（a+b）^2，（a+b）^3，（a+b）^4等展開式歸納猜想而來，並由排列組合的方法證明了這一歸納。二項式定理的性質二項式定理的係數具有對稱性。在二項式展開式中與首末兩端「等距離」的兩項的二項式係數相等；將它們繪成圖像f(x)，圖像關於x=n/2對稱，即x=n/2為圖像f(x)的對稱軸；二項式展開的中間項是二項式係數的最大值。
  • LeetCode 例題精講 | 16 最大子數組和:子數組類問題的動態規劃技巧
    Maximum Length of Repeated Subarray 最長公共子數組（Medium）在前面的文章中，我們分別講解了一維和二維動態規劃問題的解題步驟與基本思路。不過，僅僅掌握基本步驟是不夠的。要想熟練做出動態規劃題目，還要掌握足夠的解題技巧。
  • 二項式定理」到底有多重要?
    可惜我國古代的數學研究沒有形成系統的理論，雖然有了二項式係數的雛形，卻沒有進一步歸納出「二項式係數」的一般公式。可見我國古代的數學著重於「問題的獨立應用」，沒有形成「公理系統」的數學思維。到了16世紀的西方，「二項式係數表」已經深入人心，在眾多數學家的著作裡面已經出現。1654年，數學家帕斯卡，建立了「一般正整數次冪」的二項式定理。經過無數數學家的努力，「二項式定理」穿過歲月的長河，歷經風雨，終於完美出爐。1665年，牛頓在前人的研究成果上創立了現代的「二項式定理」。
  • 高中數學:二項式定理的常見題型總結
    ，但當二項式係數與各項係數只有正負差別時，可考慮係數最大項必在正數項中選擇，簡化計算．(2)理解二項式係數的有關性質，不僅在於性質本身，而且要掌握其性質背後體現的數學思想方法．有時候還要充分體現「賦值法」的應用，這是與二項式係數的性質有關的問題求解中經常使用的方法．
  • 二項式法與需要係數法比較
    2017年3月19日，筆者提出了民用建築中有些場所可以採用二項式法進行負荷計算，文章給出具體建議：民用建築中的冷凍站等大負荷場所
  • 2018高考數學二項式定理的題型總結
    同學們好，二項式定理是理科生的專利，當然理科生需要總結歸納二項式定理有哪些題型和變形。今天小新老師就將這些知識總結歸納出來，以供參考借鑑。題型一、通項係數問題 這類問題一般是求解常數項是多少？或者某一項的係數是多少？
  • 《「楊輝三角」與二項式係數的性質》教學設計
    師生活動：教師介紹教學過程3：師：「楊輝三角」中蘊含著許多二項式係數規律，你能發現哪些？你能證明嗎？性質歸納：對稱性：每行兩端都是1 ；與首末兩端「等距離」的兩個二項式係數相等. （運用組合數性質1證明）傳遞性：從第二行起，每行除1以外的每一個數都等於它肩上的兩個數的和。（運用組合數性質2證明）增減性及最值：每一行的數都是先增後減，中間的數最大。
  • 高中二項式定理在新題型中的運用
    題型我們經常碰到的題都是運用二項式定理來求展開式的第幾項或者是第幾項的係數，只需要根據二項展開式的通項公式來求解即可。所以這道題，我們要先將(x+a)^9變形，然後再利用二項式定理求解即可。具體做法第一步，將(x+a)^9變形。(x+a)^9=(x+1+a-1)^9.
  • 利用楊輝三角形來解釋二項式定理
    其中從 n 個元素中選取 k 個元素的組合公式為：二項式定理其實是一個二項多項式乘以自己 n 次最後展開得到的結果。下面就是一個抽象展開式，說明如何將二項式相乘 n 次的結果。實際上，這樣教科書般的展示方式很難閱讀。
  • 一天一道高考題094二項式定理
    二、【擬定方案】結果中x平方由兩個部分構成，一個是6次方的二項式中的x平方與前面一個式子的常數乘積的結果，另外一個是6次方的二項式中的x的4次方與前面一個式子的x的平方分之一乘積的結果，即：三、【執行方案】四、【題型總結】
  • 二項式模型
    二項式模型是這樣一種估價模型，它以對基礎資產價值變化的一種簡單描述為基礎，即假定在每個時間段，基礎資產價值的變化只能取兩個可能結果中的一個：上升某個百分點或下降某個百分點。　　二項式模型是用風險中性定價方法進行定價的。風險中性定價方法假設所有投資者都是風險中性的，在風險中性的經濟環境中，投資者並不要求任何的風險補償或風險報酬，這樣就不需要估計各種風險補償或風險報酬，省略了對風險定價的複雜內容；投資的期望收益率恰好等於無風險利率；投資的任何盈虧經無風險利率的貼現就是它們的現值。
  • 最大似然法估計二項式分布參數
    今天我們再來看看最大似然法如何求解二項式分布參數。1.二項式分布與似然值估計公式如在人們對兩種口味飲料無偏好時，即人們喜歡香橙口味的概率p=0.5，喜歡葡萄口味的概率p=0.5，那麼7個人中4個人喜歡香橙口味的概率為0.273。計算公式如下：
  • 高中數學二項式定理及其應用1
    一、二項式定理 二、二項展開式的通項、係數、二項式係數，尤其要注意二項展開式中係數與二項式係數的區別。三、（1+x)^n的展開式 四、題型：1、求二項展開式的常數項 2、求二項展開式的有理項 3、係數問題：求二項展開式中含x^k項的係數；求二項展開式中第幾項的係數；求二項展開式中含x^k項或第幾項的二項式係數；求二項展開式中兩項係數之比的問題；求二項展開式中係數之和的問題；二項式係數之和問題，和為2^n；4、構造「母函數」證明恆等式問題。
  • 高考數學衝刺,二項式定理的應用講解分析
    考點分析;二項式係數的性質．題幹分析：利用二項式定理展開即可得出．考點分析：二項式係數的性質．題幹分析：根據二項式展開式的通項公式，列出方程求出r的值即可得出展開式的常數項．考點分析：二項式係數的性質．題幹分析：先求出二項式的指數n，再利用展開式的通項公式求出展開式中含x2項的係數．
  • 二項式定理,這篇推送最全面,沒有之一!
    ④係數：正確區分二項式係數與項的係數：二項式係數指各項前面的組合數；項的係數指各項中除去變量的部分（含二項式係數）。⑤通項：通項②二項式係數最大值：展開式的二項式係數③二項式係數和：二項展開式中，所有二項式係數和等於