递归--递推之组合数

排列在上一篇中已经写到，是个典型的深搜题，下面是介绍的组合数，组合的基本定义是, 但是除了用这种传统的方法来求，可以用递归的方式或者是递推的方式来求，说道递推，只要会递归，就会递推了。关键的一部是递推式，可以定义一个函数func(int n, int k); 表示求的值，公式先放在这func(n, k) = func(n-1, k-1)+func(n-1,k);

意思就是在n中选去k个数的组合一个多少个，这时就要分两种情况, 一种是选出一组数中包含最后一个元素，它的值就是func(n - 1, k - 1), 就是再从剩下的n - 1个元素中来选k - 1个，还有一种就是不含最后一个元素, 那就是func(n - 1, k); 就是从剩下的n - 1个中选出k个来，剩下的就是边界问题，一个就是当k为0的时候和n=k的时候，就是，所以就是1，还有就是= 1；还有当n < k的时候为0，掌握好这些条件，写代码应该很轻松了

方法一(递归版):

 1 #include <stdio.h>
 2 
 3 int func(int n, int k)
 4 {
 5     if(k == n || k == 0)
 6         return 1;
 7     if(n == 0 || n < k)
 8         return 0;
 9     return func(n - 1, k - 1) + func(n - 1, k);
10 }
11 int main()
12 {
13     int n, k;
14     while(~scanf("%d %d", &n, &k))
15     {
16         printf("%d
", func(n, k));
17     }
18     
19     return 0;
20 }

方法二(递推版dp):

 1 #include <stdio.h>
 2 
 3 int main()
 4 {
 5     int dp[100][100];
 6     dp[1][1] = 1;
 7     for(int i = 1; i < 100; i++)
 8     {
 9         dp[i][0] = 1;
10     }
11     for(int i = 2; i < 100; i++)
12     {
13         for(int j = 1; j <= i; j++)
14             dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
15     }
16     int n, k;
17     while(scanf("%d %d", &n, &k) == 2)
18     {
19         printf("%d
", dp[n][k]);
20     }
21     return 0;
22 }