中學就學過排列,組合 ,比如 C5,2 = 10; C6,2 = 15
如果用算法實現的話,難道也要先做一連串的乘法,然后再相除嗎? 比如: C5,2 = (5*4*3*2)/(3*2)

如果數很大的話,又是乘又做除的,多牛的計算機才能搞定呢?

先看看簡單的:
2個數選2個,共有1種方法
3個數選2個,共有3種方法
4個數選2個,共有6種方法
n個數選2個,共有多少種方法?

F(n,2) = F(n-1,2) + F(n-1,1) //這樣寫看的更清楚些.

那么N個數選M出來,有多少種選擇呢?
F(N,M) = F(N-1,M) + F(N-1,M-1)
到此處,DP的遞歸解空間已經出來了.

F(N,M) = 1                                          M=0 or N=0 or N=M
F(N,M) = N                                          M=1
F(N,M) = F(N-1,M) + F(N-1,M-1)         M!=N 當然N>M


剩下的工作就是程序實現了.但是還有個小問題,就是在DP迭代的過程中是否需要記憶.在這個算法當然需要記憶.

實現的過程中,可以做些小優化,比如N=5 M=3 可以求C5,2的組合數就是要少遞歸幾次.

#include "stdafx.h"
#include <iostream>
using namespace std;

__int64 Aug[200][200] = {0};

__int64 getComposite(int m,int n)
{
    __int64 preResult0;
    __int64 preResult1;

    if (m==0 || n== 0 || m== 1 || m == n)
        return 1;
    if (Aug[m][n] != 0)
        return Aug[m][n];
    else
    {
        preResult0    = getComposite(m-1,n);
        Aug[m-1][n]   = preResult0;
        preResult1    = getComposite(m-1,n-1);
        Aug[m-1][n-1] = preResult1;
    }
    return preResult0 + preResult1;
}
int main()
{
    int count;
    int m,n;
    int m0,n0;

    cin >> n >> m;
    m0 = m >= n ? m : n;
    n0 = m >= n ? n : m;
    n0 = m0 - n0 >= n0 ? n0 : m0-n0;
    cout << getComposite(m0,n0) << endl;

    return 0;
}
//*********************************************************************************
注:其實我沒看明白......