C++求解组合数的具体实现

逃离我推掉我的手 2022-12-08 14:29 148阅读 0赞

### 文章目录 ###

*  前言
 *  问题起因
 *  组合公式
 *  公式变形
 *  递推公式
 *   *  递归实现
     *  备忘递归
     *  动态规划
     *  压缩DP
     *  其他优化
 *  总结
 *  补充
 *   *  反向递归
     *  正向递推

# 前言 #

很少写关于具体算法的总结笔记，因为很难把一个算法从头到尾的叙述清晰并且完整，容易造成误解。这次想总结一下组合数的具体实现，原因是最近总是碰见组合数，所以决定来写写，免得每次从头推导公式耽误时间。排列组合经常会作为一个问题解决方案中一部分，通常是求某个问题有多少个解，达到某种状态有多少种操作方式等等。

# 问题起因 #

今天下午解一道简单题，难度简直刷新了我的认知，其中需要用到组合数，但这仅仅是解题的一小部分，没办法，从头推导的，简单优化下，写出了如下代码：

int C(int a, int b)
    { 
        int ans = 1;
        for (int i = a; i > a - b; i--) ans *= i;
        for (int i = b; i > 1; i--) ans /= i;
        return ans;
    }

因为时间紧迫，范围也比较小，同时可以控制 `a` 和 `b` 的大小，所以临时写下的这段代码可以运行，不然这段代码会出现各种错误的。

# 组合公式 #

既然是想做总结，还是从头来看看组合公式，根据原始公式实现算法，并尝试优化它，当熟悉这个套路之后，就可以直接拿来用了，可以节省不少时间，组合公式的常见表示方式如下：

C n m = n ! m ! ( n − m ) ! = C n n − m , ( n ≥ m ≥ 0 ) C^m\_n = \\frac\{n!\}\{m!(n-m)!\} = C^\{n-m\}\_n,(n \\geq m \\geq 0) Cnm=m!(n−m)!n!=Cnn−m,(n≥m≥0)

这个公式写出来清晰多了，`n!`表示n的阶乘，计算方式为 n\*(n-1)\*(n-2)\*(n-3)\*…\*3\*2\*1， 相信很多人都清楚，我们只要把这个数据公式翻译成代码就可以了：

int C2(int n, int m)
    { 
        int a = 1, b = 1, c = 1;
        for (int i = n; i >= 1; --i) a *= i;
        for (int i = m; i >= 1; --i) b *= i;
        for (int i = n-m; i >= 1; --i) c *= i;
        return a/(b*c);
    }

代码比较简单，依次计算公式中三个数的阶乘，然后再做乘除法就可以了，但是你有没有思考过一个问题，`int` 类型的整数最大能表示的阶乘是多少？是`12!`，它的值是 479,001,600，它是 `int` 表示范围内最大的阶乘数，看来这种实现方式局限性很大，如果 n 大于12就没有办法计算了。

# 公式变形 #

实际上根据阶乘的定义，n! 和 (n-m)! 是可以约分的，将这两个式子约分后，公式可以化简为：

C n m = n ! m ! ( n − m ) ! = n ( n − 1 ) ( n − 2 ) . . . ( n − m + 1 ) ) m ! , ( n ≥ m ≥ 0 ) C^m\_n = \\frac\{n!\}\{m!(n-m)!\} = \\frac\{n(n-1)(n-2)...(n-m+1))\}\{m!\},(n \\geq m \\geq 0) Cnm=m!(n−m)!n!=m!n(n−1)(n−2)...(n−m\+1)),(n≥m≥0)

公式写成这样之后可以少计算一个阶乘，并且计算的范围也会缩小，代码实现和一开始展示的代码思想是一样的：

int C3(int n, int m)
    { 
        int a = 1, b = 1;
        for (int i = n; i > n - m; --i) a *= i;
        for (int i = m; i >= 1; i--) b *= i;
        return a/b;
    }

这段代码虽然经过了化简，但是当 n 和 m 非常接近的时候，分子还是接近于 n!，所以表示的范围还是比较小。

# 递推公式 #

直接给出的公式经过化简后还是受制于计算阶乘的范围，得想个办法看看能不能绕过阶乘计算，方法总是有的，并且前辈们已经给我们整理好了，我们总是站在巨人的肩膀上，下面就是递推公式：

\{ C n m = 1 , ( m = 0 或 m = n ) C n m = C n − 1 m + C n − 1 m − 1 , ( n > m > 0 ) \\begin\{cases\} \{C^m\_n\} = 1,\\qquad\\qquad\\qquad (m=0 或 m=n) \\\\ \{C^m\_n\} = \{C^m\_\{n-1\}\} + \{C^\{m-1\}\_\{n-1\}\},\\qquad(n > m > 0) \\end\{cases\} \{ Cnm=1,(m=0或m=n)Cnm=Cn−1m\+Cn−1m−1,(n>m>0)

## 递归实现 ##

有了上面的分段函数表示，就满足了递归的条件，既有递归调用缩小规模，也有递归出口，这样实现起来很简单，代码如下：

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

这两行代码是不是很秀？不过使用递归常常会出现一问题，那就是相同子问题多次计算，导致效率低下，这个计算组合数的方式同样存在重复计算子问题的缺点，我们以调用C4(5, 3)为例，看看下面的调用关系图：

5,3

4,3

3,3

3,2

2,2

2,1

1,1

1,0

4,2

3,2

3,1

2,2

2,1

2,0

1,1

1,0

1,1

1,0

从这个图可以清晰看出`C4(3, 2)` 和 `C4(2, 1)` 都被计算了多次，当 m 和 n 的数字比较大的时候，会进行更多次的重复计算，严重影响计算的效率，有没有什么办法解决重复计算的问题呢？

## 备忘递归 ##

解决重复计算的常用方法是利用一个备忘录，将已经计算式子结果存储起来，下次再遇到重复的计算时直接取上次的结果就可以了，我们可以将中间结果简单存储到map中。

假设 n 不超过10000，这比12已经大太多了，我们可以使用 `n * 10000 + m` 作为map的键，然后将结果存储到map中，每次计算一个式子前先看查询备忘录，看之前有没有计算过，如果计算过直接取结果就可以了，代码简单实现如下：

int C5(int n, int m, map<int, int>& memo)
    { 
        if (n == m || m == 0) return 1;
    
        auto itora = memo.find((n-1)*10000+m);
        int a = itora != memo.end() ? itora->second : C4(n-1, m);
        if (itora == memo.end()) memo[(n-1)*10000+m] = a;
    
        auto itorb = memo.find((n-1)*10000+m-1);
        int b = itorb != memo.end() ? itorb->second : C4(n-1, m-1);
        if (itorb == memo.end()) memo[(n-1)*10000+m-1] = b;
    
        return a + b;
    }

使用 map 作为备忘录可以避免重复计算，这是解决递归效率低下的常用方法，那么有了递推公式不使用递归实现可不可以呢？当然可以了，针对于这个问题，有了递推公式我们还可以使用动态规划（dp）的方式来实现。

## 动态规划 ##

动态规划常常适用于有重叠子问题和最优子结构性质的问题，试图只解决每个子问题一次，具有天然剪枝的功能。基本思想非常简单，若要解一个给定问题，我们需要解其不同子问题，再根据子问题的解以得出原问题的解。

再回顾一下递推公式：

翻译成人话就是，当m等于0或者等于n的时候，组合数结果为1，否则组合数结果等于另外两个组合数的和，我们可以采用正向推导的方式，将 n 和 m 逐步扩大，最终得到我们想要的结果，定义dp表格如下：

从表格可以清晰的看出求解 `C(5,3)` 只需要计算5行3列（从0开始）的数据，其余的值可以不用计算，这样我们就可以对照着表格写代码啦，定义一个dp数组，然后双重for循环就搞定了：

int C6(int n, int m)
    { 
        if (n == m || m == 0) return 1;
    
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= i && j <= m; j++)
                if (i == j || j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
    
        return dp[n][m];
    }

至此，我们就采用了非递归的方式求解出了组合数的结果，但是这里的空间有点浪费，每次都要花费`O(mn)`的空间复杂度，有没有办法降低一点呢？我们可以找找规律进行压缩。

## 压缩DP ##

观察之前的动态规划实现的代码，我们发现求解第 `i`行的数据时只与第 `i-1` 行有关，所以我们可以考虑将二维数据压缩成一维，还是逐行求解，只不过可以用一维数组来记录求解的结果，优化代码如下：

int C7(int n, int m)
    { 
        if (n == m || m == 0) return 1;
    
        vector<int> dp(m+1);
        for (int i = 0; i <= n; i++)
            for (int j = min(i, m); j >= 0; j--)
                if (i == j || j == 0) dp[j] = 1;
                else dp[j] = dp[j] + dp[j-1];
    
        return dp[m];
    }

这样我们就将空间复杂度降低到了`O(m)`，需要注意的是在计算dp时，因为采用了压缩结构，为防止前面的修改影响后续结果，所以采用里倒序遍历，这是一个易错的点。

## 其他优化 ##

代码实现到这里，我们的时间复杂度是`O(nm)`，空间复杂是`O(m)`，其实还有进一步的优化空间：

*  **减小m：** 因为题目是求解C(n, m)，但是我们知道组合公式中，C(n, m) 和 C(n, n-m) 相等，所以当 n-m 小于 m 的时候求解C(n, n-m)可以降低时间复杂度和空间复杂度。
 *  **部分剪枝：** 观察函数`int C7(int n, int m)`，实际上当i为n时，j没必要遍历到0，只需要计算j等于m的情况就可以了，可以提前计算出结果。
 *  **缩小计算范围：** 从上面的剪枝操作得到启示，其实每一行没必要全部计算出来，以 `C(5,3)` 为例，我们只需要计算出表格中有数字的位置的结果就可以了：

这样来看每行最多需要计算3个值，那么时间复杂度可以降低到 `O(3n)`，去掉常数，时间复杂度降为 `O(n)`。

# 总结 #

*  计算组合数可以采用逆向递归和正向递推两种方式，递归时注意写好递归出口
 *  采用正向递推方法时利用动态规划思想，使用子问题的解拼凑出最终问题的解
 *  计算组合数若使用了计算阶乘应注意范围，避免在计算时产生溢出，`int`最多能表示 `12!`
 *  使用动态规划方法时可以逐步优化空间和时间，这其实就是优化算法的过程，也是提升的过程
 *  关于组合数的求解方式，我们可以找到时间复杂度`O(n)`、空间复杂度`O(m)`的非递归解法

# 补充 #

感谢 `@小胡同的诗` 同学的补充和提醒，让我再次感受到数学力量的深不可测，原来求解组合数还有这样一个递推公式：

\{ C n m = 1 , ( m = 0 或 m = n ) C n m = n − m + 1 m C n m − 1 , ( n > m > 0 ) \\begin\{cases\} \{C^m\_n\} = 1,\\qquad\\qquad\\qquad (m=0 或 m=n) \\\\ C\_n^m=\\frac\{n-m+1\}\{m\}C\_n^\{m-1\},\\qquad(n > m > 0) \\end\{cases\} \{ Cnm=1,(m=0或m=n)Cnm=mn−m\+1Cnm−1,(n>m>0)

这个公式厉害就厉害在它是一个线性的，不存在分叉的情况，也就是说即使递归也不会出现重复的计算，我们简单实现一下。

## 反向递归 ##

int C8(int n, int m)
    { 
        if (n == m || m == 0) return 1;
        return C8(n, m-1) * (n-m+1) / m;
    }

代码非常紧凑，也不存在重复计算的情况，当然我们也可以使用正向计算的方式来实现。

## 正向递推 ##

int C9(int n, int m)
    { 
        if (n == m || m == 0) return 1;
    
        int ans = 1;
        m = min(m, n-m);
    
        for (int i = 1; i <= m; i++) ans = ans * (n-i+1) / i;
        return ans;
    }

这段代码将时间复杂度降到了O(m)，空间复杂度降到了O(1)，不过特定的场景还是要选择特定的实现，虽然`C9`函数在时间复杂度和空间复杂度上都优于 `C5` 函数，但是如果一个实际问题中需要用到多个组合数的时候，`C5` 这种采用缓存的方式可能会是更好的选择。

--------------------

[ ==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<== ][_ _]

--------------------

> 想讲故事？没人倾听？那是因为你还未到达一个指定的高度，当你在某个领域站稳了脚跟，做出了成绩，自然有的是时间去讲故事或者“编”故事，到时候随便一句话都会被很多人奉为圭臬，甚至会出现一些鸡汤莫名其妙的从你嘴里“说”出来。在你拥有了讲故事权利的同时，批判的声音也将随之而来~

[_ _]: https://blog.csdn.net/albertsh/article/details/108552268