組合數定義:從m個不同元素中，任取n(n≤m)個元素并成一組，叫做從m個不同元素中取出n個元素的一個組合；從m個不同元素中取出n(n≤m)個元素的所有組合的個數，叫做從m個不同元素中取出n個元素的組合數。
下面是一種比較通俗的計算公式:
其遞歸公式為:
c(n,m)=c(n-1,m-1)+c(n-1,m)
下面是c++實作該遞歸算法:
java版:
但是在反複遞歸調用的時候,我們發現重複計算了一些值,可能這麼看是看不出什麼,下面用一張圖來說明其調用過程:
我隻畫了部分,如果該組合數足夠大的話,那麼在遞歸調用的過程中則會有很多重複計算,效率是十分低的,是以在求類似問題的時候,我們都會去實用動态規劃來求解.那什麼是動态規劃呢?
動态規劃算法,其基本思想也是将待求解問題分解成若幹個子問題，先求解子問題，然後從問題的解得到原問題的解。與分治法不同的是，适合于用動态規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重複計算了很多次。如果我們能夠儲存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重複計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，隻要它被計算過，就将其結果填入表中。這就是動态規劃法的基本思路。具體的動态規劃算法多種多樣，但它們具有相同的填表格式。
是以,在實用動态規劃的算法中,這個臨時線性表是非常重要的,該表是一個二維數組;
下面是c++版:
從上面的程式可以看出,使用動态規劃的時候,我們必須對所求問題的子結構了解的很透徹,在分解組合數的時候,它的兩個子結構之間并不像分治算法那樣互相獨立,之間基本上是互相包含的,是以,如果使用遞歸,則其子結構在調用的時候,另一個子結構則會重複該子結構中已經存在的過程,如果m和n足夠大的時候,重複率我們無法接受,是以這個使用使用動态規劃則能很好的解決問題,盡管在算法的實作上有些麻煩,但是在很大程度上減少空間和時間複雜度,這一點,還是很讓人值得嘗試.
使用動态規劃的核心是我們必須有一個容器來儲存計算過程中産生的結果,而且這個容器是随着問題域大小二動态變化的.有時候會是一個棧,有時候是一個線性表,如果問題更複雜,則會是一個動态樹或圖.