poj1664 - 放苹果

题目链接：点击打开链接

题目意思：

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

思路：

当n>=m时，必定有n-m个盘子空着，f(m, n)等价于f(m, m) 当n<m时，有两种情况： （1）至少有1个盘子空着, f(m, n)等价于f(m, n-1) （2）至少每个盘子都有一个苹果,f(m, n)等价于f(fm-n, n) 疑问：重复的问题是如何解决的？ 启示： 递归的转换 代码： #include <iostream> #include <cstdio> using namespace std; int dfs(int m, int n){ if(m==0 || n==1) return 1; if(n>m) return dfs(m, m); else return dfs(m-n, n) + dfs(m, n-1); } int main(){ int t, m, n; scanf("%d", &t); while(t--){ scanf("%d%d", &m, &n); printf("%d\n", dfs(m, n)); } return 0; }