咖啡


私信TA

用户名:Tianxn

访问量:128018

签 名:

十年OI一场空,不开LL见祖宗。

等  级
排  名 8
经  验 26039
参赛次数 10
文章发表 197
年  龄 22
在职情况 学生
学  校 西安电子科技大学
专  业 软件工程

  自我简介:

解题思路:

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;
}


 

0.0分

6 人评分

  评论区

这种动态规划该怎么去想了?
2022-01-27 15:21:57
  • «
  • 1
  • »