组合数

组合数常常用来解决一些选择类型的数学问题。

从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。

组合数的数学公式

组合数的定义公式(1)

!%7D%20%3D%20C%7Bn%7D%5E%7Bn-m%7D%20%5Ctag%7B1%7D%0A#card=math&code=C%7Bn%7D%5E%7Bm%7D%20%3D%20%5Cfrac%7Bn%21%7D%7Bm%21%28n-m%29%21%7D%20%3D%20C_%7Bn%7D%5E%7Bn-m%7D%20%5Ctag%7B1%7D%0A)

通过观察杨辉三角可以得到公式(2)

组合数的代码实现

通过公式(2)可以考虑通过递归和递推的方式来计算组合数，考虑到尽可能的表示大一些的数，采用long long来进行存储数据。

递归方式

long long getCombin(int n, int m) {
    if(m == 0 || m == n) return 1;
    return getCombin(n-1, m-1) + getCombin(n-1, m);
}

递归改进

在递归过程中有许多部分重复计算，考虑把中间结果进行保存，使用时查询，以空间换时间。

const int tableSize = 67;
vector<vector<long long>> combinTable(tableSize, vector<long long>(tableSize, 0));
long long getCombin(int n, int m) {
    if(m == 0 || m == n) return 1;
    else if(combinTable[n][m] != 0) return combinTable[n][m];
    return combinTable[n][m] = getCombin(n-1, m-1) + getCombin(n-1, m);
}

递推方式+打表

const int tableSize = 67;
vector<vector<long long>> combinTable(tableSize, vector<long long>(tableSize, 0));
void buildCombinTable() {
    for(int i = 1; i < tableSize; ++ i) {
        combinTable[i][i] = combinTable[i][0] = 1;
    }
    for(int i = 2; i < tableSize; ++ i) {
        for(int j = i/2; j > 0; -- j) {
            combinTable[i][j] = combinTable[i-1][j-1] + combinTable[i-1][j];
            combinTable[i][i-j] = combinTable[i][j];
        }
    }
}
long long getCombin(int n, int m) {
    return combinTable[n][m];
}

数学公式优化

!%7D%20%3D%26%20%5Cfrac%7B(n-m%2B1)%5Ctimes(n-m%2B2)%5Ctimes%20%5Ccdots%20%5Ctimes(n-m%2Bm)%7D%7B1%20%5Ctimes%202%20%5Ctimes%20%5Ccdots%20%5Ctimes%20m%20%7D%20%5C%5C%0A%3D%26%5Cfrac%7Bn-m%2B1%7D%7B1%7D%20%5Ctimes%20%5Cfrac%7Bn-m%2B2%7D%7B2%7D%20%5Ctimes%20%5Ccdots%20%5Ctimes%20%5Cfrac%7Bn-m%2Bm%7D%7Bm%7D%20%0A%0A%5Cend%7Baligned%7D%20%5Ctag%7B3%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AC_%7Bn%7D%5E%7Bm%7D%20%3D%20%5Cfrac%7Bn%21%7D%7Bm%21%28n-m%29%21%7D%20%3D%26%20%5Cfrac%7B%28n-m%2B1%29%5Ctimes%28n-m%2B2%29%5Ctimes%20%5Ccdots%20%5Ctimes%28n-m%2Bm%29%7D%7B1%20%5Ctimes%202%20%5Ctimes%20%5Ccdots%20%5Ctimes%20m%20%7D%20%5C%5C%0A%3D%26%5Cfrac%7Bn-m%2B1%7D%7B1%7D%20%5Ctimes%20%5Cfrac%7Bn-m%2B2%7D%7B2%7D%20%5Ctimes%20%5Ccdots%20%5Ctimes%20%5Cfrac%7Bn-m%2Bm%7D%7Bm%7D%20%0A%0A%5Cend%7Baligned%7D%20%5Ctag%7B3%7D%0A)

显然，前k项可以看作是的展开，因此分子分母必定可以整除，所以可以从左到右依次进行计算，先乘后除。

long long getCombin(int n, int m) {
    int ans = 1;
    for(long long i = 1; i <= m; ++ i) {
        ans = ans * (n-m+i) / i; // ans *= (n-m+1) /i; is wrong!
    }
    return ans;
}

练习题

一道看穿本质考察组合数的DP题目。

DP - 路径问题 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)