题目描述
把 M 个同样的苹果放在 N 个同样的盘子里, 允许有的盘子空着不放, 问共有多少种不同的分法?(用 K 表示)5,1,1 和 1,5,1 是同一种分法.
输入输出格式
输入格式
一行, 包含二个整数 M 和 N, 以空格分开.(1≤M,N≤100)
输出格式
一行, 一个整数 K, 可行的方案数.
输入输出样例
输入样例
7 3
输出样例
8
题解
用 $a[i][j]$ 表示 $i$ 个苹果放 $j$ 个盘子, 易得有两种情况: 一是不放第 $j$ 个盘子, 一是放第 $j$ 个盘子即放满所有盘子, 得 $a[i][j]=a[i][j-1]+a[i-j][j]$.
- #include <iostream>
- #define MAX_M 101
- #define MAX_N 101
- using namespace std;
- int m, n;
- int a[MAX_M][MAX_N];
- int main()
- {
- cin>> m>> n;
- for(register int i = 0; i <= m; i++) for(register int j = 1; j <= n; j++)
- {
- if(i < 1 || j < 2) a[i][j] = 1;
- else if(i < j) a[i][j] = a[i][i];
- else a[i][j] = a[i - j][j] + a[i][j - 1];
- }
- cout << a[m][n];
- return 0;
- }
参考程序
来源: http://www.bubuko.com/infodetail-3013253.html