数的划分C++代码

解题思路:

f[n][m]表示“将n分为m个正整数”的划分数：

m>n时：f[n][m]=0；

m=1或n==m时：f[n][m]=1；

m<n时：
a) 有1的时候就相当于有一个抽屉已经确定了并且那个抽屉里就是1，所以这个时候分法就等于把n-1分在m-1个抽屉里即 f[n-1][m-1]；
b) 没有一个抽屉是1，可以往每个抽屉里的都先放上一个1，方法数就相当于把剩下的数n-m分到m个抽屉里即f[n-m][m]；因此f[n][m]= f[n-1][m-1]+ f[n-m][m]。

参考代码:

#include <iostream>
#include <cstring>
using namespace std;

int f[105][105];

int dfs(int n, int k)
{
	if (n < k) return 0;
	if (f[n][k] != -1) return f[n][k];
	if (k == 1 || n == k) return 1;
	return f[n][k] = dfs(n - k, k) + dfs(n - 1, k - 1);
}

int main()
{
	int n, res = 0;
	cin >> n;
	memset(f, -1, sizeof f);
	for (int i = 1; i <= n; i++)
		res += dfs(n, i);
	cout << res << endl;
	return 0;
}