请问一道与集合划分有关的动态规划问题。。
题目描述:有n颗糖,品种不一。把这n颗糖分堆,请问有多少种方案?(假设每堆至少1颗糖,最多3颗糖)
输入格式:
多组测试数据,每行输入一个n(0<=n<=20),表示有n颗糖。
输出格式:
输出方案数,每组输出占一行。
输入样例:
1
2
输出样例:
1
2
注意:分好了的堆与堆之间是无序的。
[此贴子已经被作者于2018-11-21 13:07编辑过]
#include <iostream> using namespace std; int main( void ) { unsigned long long f[21] = { 1, 1 }; for( size_t i=2; i!=21; ++i ) f[i] = f[i-1]*1 + f[i-2]*(i-1) + f[i-3]*((i-1)*(i-2)/2); for( size_t n; cin>>n; ) cout << f[n] << '\n'; }