解题思路:
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 人评分
点我有惊喜!你懂得!浏览:2213 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:544 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:632 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:619 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:724 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:763 |
【蟠桃记】 (C语言代码)浏览:664 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:500 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:504 |
罗列完美数 (C语言代码)浏览:491 |