動態編程：二項式序列

本文為 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 實現的遍歷解法如下圖所示：

二項式序列--遍歷解

運行的結果如下圖所示：

輸出結果

繼續編程！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！