DP算法求组合数

中学就学过排列,组合 ,比如 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;
}
//*********************************************************************************
注:其实我没看明白......