解题思路:
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 人评分
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:593 |
打水问题 (C语言代码)浏览:1055 |
1024题解浏览:802 |
1051(奇了怪了)浏览:645 |
模拟计算器 (C语言代码)浏览:2285 |
复数求和 (C语言代码)浏览:915 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:498 |
拆分位数 (C语言代码)浏览:441 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:695 |
1199题解浏览:653 |