很少写关于具体算法的总结笔记，因为很难把一个算法从头到尾的叙述清晰并且完整，容易造成误解。这次想总结一下组合数的具体实现，原因是最近总是碰见组合数，所以决定来写写，免得每次从头推导公式耽误时间。排列组合经常会作为一个问题解决方案中一部分，通常是求某个问题有多少个解，达到某种状态有多少种操作方式等等。
今天下午解一道简单题，难度简直刷新了我的认知，其中需要用到组合数，但这仅仅是解题的一小部分，没办法，从头推导的，简单优化下，写出了如下代码：
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)
C n m = m ! ( n − m ) ! n ! = C n n − 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)
C n m = 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}
{ C n m = 1 , ( m = 0 或 m = n ) C n m = C n − 1 m + C n − 1 m − 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,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）的方式来实现。
动态规划
动态规划常常适用于有重叠子问题和最优子结构性质的问题，试图只解决每个子问题一次，具有天然剪枝的功能。基本思想非常简单，若要解一个给定问题，我们需要解其不同子问题，再根据子问题的解以得出原问题的解。
再回顾一下递推公式：
{
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}
{ C n m = 1 , ( m = 0 或 m = n ) C n m = C n − 1 m + C n − 1 m − 1 , ( n > m > 0 )
翻译成人话就是，当m等于0或者等于n的时候，组合数结果为1，否则组合数结果等于另外两个组合数的和，我们可以采用正向推导的方式，将 n 和 m 逐步扩大，最终得到我们想要的结果，定义dp表格如下：
n\m (0) (1) (2) (3) (4) (5) (0) 1 (1) 1 1 (2) 1 2 1 (3) 1 3 3 1 (4) 1 4 6 4 <1> (5) 1 5 10 ==>10 <5> <1>
从表格可以清晰的看出求解 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) 为例，我们只需要计算出表格中有数字的位置的结果就可以了：
n\m (0) (1) (2) (3) (4) (5) (0) 1 (1) 1 1 (2) 1 2 1 (3) 3 3 1 (4) 6 4 (5) ==>10
这样来看每行最多需要计算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}
{ C n m = 1 , ( m = 0 或 m = n ) C n m = m n − m + 1 C n m − 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 这种采用缓存的方式可能会是更好的选择。
==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==
想讲故事？没人倾听？那是因为你还未到达一个指定的高度，当你在某个领域站稳了脚跟，做出了成绩，自然有的是时间去讲故事或者“编”故事，到时候随便一句话都会被很多人奉为圭臬，甚至会出现一些鸡汤莫名其妙的从你嘴里“说”出来。在你拥有了讲故事权利的同时，批判的声音也将随之而来~
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
