通过分类讨论,将规模较大的问题转换成规模较小的相同问题,学会”降维“,将索引值不断降小,就可以递归求解
设f(m,n)为把m个苹果放到n个盘子中的方法数,m>=0,n>=0.
若m和n中任何一个等于0,那么f(m,n) = 1,注意不是等于0,因为相当于就那么一种结果,就是不往盘子里面放(没有苹果),或者,连盘子都没有。
若n=1,显然对于任意的m>=0 有f(m,1) = 1
若m=1,显然对于任意的n>=0 有f(1,n) = 1
接下来讨论m>1 && n>1的情况:
若 m < n 则 f(m,n) = f(m,m)。即空哪几个盘子都是一样的
若 m>=n 则 大体有两种放法:
第1种情况:至少有一个盘子为空,即什么也不放,这部分的方法数为f(m,n-1);
第2种情况:全部盘子都有苹果,那么先从m个苹果中抽取出n个出来,各个盘子分一个,考虑剩下的m-n个苹果放到n个盘子里的放法,这样就成功把f(m,n)降到了f(m-n,n)。
所以,m>=n时,有f(m,n) = f(m,n-1) + f(m-n,n);
Source Code
Problem: 1664
|
|
User:
yangliuACMer
|
Memory: 384K |
|
Time: 0MS |
Language: GCC |
|
Result: Accepted
|
分享到:
相关推荐
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
poj 1664 放苹果.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj分类poj分类poj分类poj分类
POJ题目分类POJ题目分类POJ题目分类
poj 百练 题目分类 poj 百练 题目分类
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
poj题目分类
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
强大的poj分类 学做POJ必备 非最新,供参考
poj题目分类打包 acm北大的题库题目分类 来源网络 网络还有自己整理一部分。好久前的玩意了
pojACM题目分类,便于各类型同学分别做题有所参考
poj 2893 M × N Puzzle.md
北大POJ2002-Squares 解题报告+AC代码
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
POJ3273 Monthly Expense题解 题目分析: 给出N个数,要求你合并连续的数,使其合并在满足不差过M个合并后的集合的时候,不超过M个集合的和的最大值最小。
北大POJ3087-Shuffle'm Up 解题报告+AC代码
史上最全poj题目分类(159页).pdf
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类