划分数问题——盘子与小球——排列组合——递推式思维转化

0#引入

考试时遇到同球同盘的问题，一开始想用插板法，终究失败，只拿了20分，回家问了老师，老师告了我方法并让我自己研究剩下三种。

1#同球同盘——递推或递归（+记忆化改进优化）

这个我有真题http://www.kencoding.net/problem.php?id=1369，大家可以去做一下

我先把递推公式列在这里：
（n是球数，m是盘子数）
$$\{\begin{array}{l}f(0,0)=1\\ f(n,1)=1\\ f(n,m)=f(n,n)if(n<m)\\ f(n,m)=f(n-m,m)+f(n,m-1)if(n\ge m)\end{array}$$

第一个是人为修正的，后两个是可以理解的，第三个我来解释一下：

如果n大于等于m时，那么分为两种情况（1）放满盘子；（2）有空盘。

（1）$f(n-m,m)$的意思是：既然要将球放满，那么就从每个盘子里拿走一个球，即球数减盘子数，剩下的球在其中继续排列结果是不变的，因为同球同盘嘛。如果第一次每个盘子取一个之后球数仍然大于盘子数，那么将会在第二次再次执行每个盘子去一个球的操作。
（2）$f(n,m-1)$的意思是：有空盘的话，就先拿走一个盘子，剩下的球在剩下的盘子中排列，直到盘子数减到1。

0的特殊情况：我们来看一个实例，按照我们的公式，f(2,2)会执行如下操作：

$$f(2,2)=f(0,2)+f(2,1)=f(0,0)+1=?+1$$

我们实际算一下，f(2,2)应该是2，那么f(0,0)是多少呢？？？只能是一了，所以我就这么尴尬的定下来了。

下面我给出代码，这道题可以AC该题目：

（1）递推版本：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, p;
int dp[1010][1010];
int main()
{cin >> n >> m >> p;for (int i = 1; i <= 1001; i++){dp[i][1] = 1;// dp[0][i] = 1;}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (i < j)dp[i][j] = dp[i][i];else if (i > j){dp[i][j] = (dp[i][j - 1] + dp[i - j][j]) % p;}else if (i == j){dp[i][j] = (1 + dp[i][j - 1]) % p;}}}cout << dp[n][m] << endl;return 0;
}

严谨一些我们可以加上一些初始化比如memset

（2）递归版本，会超时

#include <iostream>#include <cstring>
#include <cstdio>using namespace std;
int p;
int f(int n, int m)
{if (m == 1)return 1;if (n == 0)return 1;if (m > n)return f(n, n) % p;if (m <= n){return (f(n, m - 1) + f(n - m, m)) % p;}
}int main()
{int n, m;cin >> n >> m >> p;cout << f(n, m) % p << endl;return 0;
}

为什么会超时呢？这就像我们的经典例题斐波那契数列了，我们会发现有很多的重复调用，所以我们需要用数组来解决问题，也就是记忆化搜索，而改变为记忆化搜索之后递归也就从根本上和递推是一个道理了，可以统称为动态规划了。

（3）数组改版递归，记忆化搜索

#include <iostream>#include <cstring>
#include <cstdio>using namespace std;
int p;
int dp[1010][1010];
int f(int n, int m)
{if (m == 1)return 1;if (n == 0 && m == 0)return 1;if (m > n)return f(n, n) % p;if (m <= n && dp[n][m] == -1){dp[n][m] = (f(n, m - 1) + f(n - m, m)) % p;return dp[n][m];}else{return dp[n][m];}
}int main()
{int n, m;memset(dp, -1, sizeof(dp));for (int i = 1; i <= 1001; i++){dp[i][1] = 1;dp[0][i] = 1;}cin >> n >> m >> p;cout << f(n, m) % p << endl;return 0;
}

AC散花。

错误总结：
不能忘记取模的优先级，一定要加括号，一直因为这个小问题耽误了60分！！！

2#异球同盘——递归

n个各不相同的球放在m个相同的盘子里，问所有情况有多少种？

递推（归）公式：

这个递推公式是用来算全放满的可能性的
$$\{\begin{array}{l}f(n,1)=1\\ f(n,0)=1\\ f(n,m)=1if(n=m)\\ f(n,m)=f(n-1,m-1)+f(n-1,m)\times mif(n\ge m)\end{array}$$

有了这个递推公式，那么就可以把盘子数从小到大循环上去，每次调用一个对应的函数，然后累加结果，就是答案了。

解释：

（1）$f(n,1)=1$ 和 $f(n,0)=1$可以理解
（2）$f(n,m)=1$因为必须全放满，而且因为是异球同盘，所以n=m时只能有一种情况。
（3）最后的关系式：分为两个步骤，首先我们先去掉一个球和一个盘子，就是f(n-1,m-1)，使得单独的一个小球与盘子独立，然后算剩下的小球在剩下的盘子里面的排法；但是这样不能使得排法全面，所以我们暂时将盘子放回来，变成m个盘子，小球还在外面，算n-1个球在m个盘子中的排法，为什么要乘m？因为最后一个小球还要放进来，小球可以放在m个位置，而没放在一个位置，都会对应着所有的排法的改变，故乘m。为什么要这么干呢？因为这样可以使得状态逐步向n<m发展，也能计算有堆叠球的情况，这就是状态转移的概念。

/*
问题描述：
n个不同的球放在m个同样的盘子中
允许空盘：（大于） 分别计算0个、1个、2个...n-1个空盘的数值，并求和 
不允许空盘：题解函数 
盘子相同的情况下，如果盘子比球多，则忽略多余的盘子 
解法思路：根据第一个小球的情况分情况递归（独自一盘，与它球共处一盘） 
*/
#include <iostream>
#include <algorithm>
using namespace std;
int ballPlate2(int ballNum, int plateNum)
{if (plateNum == 1){return 1;}if (plateNum < 1){return 0;}if (ballNum == plateNum){return 1;}if (ballNum < plateNum){return 0;}int a1, a2;a1 = ballPlate2(ballNum - 1, plateNum - 1);a2 = ballPlate2(ballNum - 1, plateNum);return a1 + a2 * plateNum;
}
int ballPlate2_empty(int ballNum, int plateNum)
{int sum = 0;for (int i = 0; i <= plateNum; i++){int a = ballPlate2(ballNum, i); // 盘子数不断增加算每一种sum += a; // 累加结果，即为所有结果}return sum;
}
int main()
{cout << ballPlate2(4, 3) << endl; // 全放满的结果cout << ballPlate2_empty(4, 3) << endl; // 所有结果return 0;
}

也可以加上记忆化优化。。。

3#同球异盘——插板法

这道题倒是用不到递推，我们可以用简单的排列组合插板法解决

也就是将m-1个板子插到n-1个空档中。用程序中的full_f()函数解决，但这个只能算出全放满的可能性。

要算出所有结果，我一开始写的是循环，但是错了，其实有一个非常简单的方法直接去算(n + m - 1, m - 1)的插板就行了。我们可以这么理解，插板法都是插在球的内部，那为了插出空盘，就可以将空档增加，增加到盘子外面，这样就有了额外的空档，可以插出空盘，也可以插出全满。

#include <iostream>using namespace std;
int n, m;
int full_f(int n, int m)
{int a = 1;for (int i = 1; i <= m; i++){a *= (n - i + 1);}for (int i = 1; i <= m; i++){a /= i;}return a;
}
int d(int n, int m)
{return full_f(n + m - 1, m - 1);
}
int main()
{cin >> n >> m;cout << full_f(n - 1, m - 1) << endl; // 放满结果cout << d(n, m) << endl; //所有结果return 0;
}

4#异球异盘——最简单的mⁿ

既然是异球异盘，我们可以看出来每一个球都有m个选择，每个球还不怕重复，所以n个球m个盘子，那么结果就是mⁿ

#include <iostream>
#include <math.h>
using namespace std;
int binPow(int n, int m) // 快速幂
{int result = 1;while (m != 0){if (m % 2 != 0)result *= n;n *= n;m /= 2;}return result;
}
int fac(int n) // 阶乘factorial
{int ans = 1;for (int i = 1; i <= n; i++){ans *= i;}return ans;
}int f(int n, int m) // 这是异球同盘的程序
{if (m == 1)return 1;else if (m == 0)return 0;if (n == m)return 1;else if (n < m)return 0;if (n >= m){int a1 = f(n - 1, m - 1);int a2 = f(n - 1, m) * m;return a1 + a2 * m;}
}int bp_empty(int ballNum, int plateNum)
{return binPow(plateNum, ballNum);
}
int bpf(int ballNum, int plateNum)
{int b = f(ballNum, plateNum);int a = fac(plateNum);return a * b; // 将盘子的排法和异球同盘相乘
}int main()
{int n, m;cin >> n >> m;cout << bpf(n, m) << endl; // 全放满cout << bp_empty(n, m) << endl; // 所有情况,m^nreturn 0;
}

5#总结

这四个题目的程序思维都不一样，都需要思考很久，有时想了很久都想不出来，出去休息一会回来突然就有了新的思路。。