98 数的划分

98 数的划分

作者: Turbo时间限制: 1S章节: 动态规划

问题描述 :

  将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
  例如:n=7,k=3,下面三种分法被认为是相同的。
  1,1,5; 1,5,1; 5,1,1;
  问有多少种不同的分法。

样例输入

7 3

样例输出

4 {四种分法为:1,1,5; 1,2,4; 1,3,3; 2,2,3;}

输入说明 :

两个整数n和k

6<n<=200,2<=k<=6

输出说明 :

一个整数,即不同的分法

输入范例 :
7 3
输出范例 :
4

dp:
分两种情况 1, 至少一个盒子只有一个球的个数 2,没有一个盒子只有一个球
这样进行划分的原因是这种分类足够特殊,1和2都有可以写出来的表达式:

  1. 因为盒子不加区分,那么1的情况数与“将n-1个小球放到k-1个盒子中”的情况数一样
  2. 没有一个盒子只有一个小球,那么把每个盒子中拿出来一个小球,对应的是“把(n-k)个小球放到k个盒子中的情况数”
    至于1和2中的两种等价关系为什么成立,可以用集合A=集合B的方式去证明
#include <iostream>
using namespace std;
int main()
{
	int n, k;
	cin >> n >> k;
	int dp[201][201] = { 0 };
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (i == j)
				dp[i][j] = 1;
			else
				dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
		}
	}
	cout << dp[n][k] << endl;
	return 0;
}

dfs:

#include <iostream>
using namespace std;
int n, m,num=0;
void dfs(int k, int sum, int index)
{
	if (index == m)
	{
		if (sum == n)
			num++;
		return;
	}
	for (int i = k; sum + i*(m - index) <= n; i++)//剪枝
	{
		dfs(i, sum + i, index + 1);
	}
}
int main()
{
	cin >> n >> m;
	dfs(1, 0, 0);
	cout << num << endl;
	return 0;
}
上一篇:如何实现窗口中子控件的绘图(paintEvent())事件


下一篇:C++基础之C++学习简介