这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
//ID:百练OJ 1664 放苹果 //地址:http://www.cppleyuan.com/ //个人主页:www.wutianqi.com //豆瓣小组:http://www.douban.com/group/cppleyuan/
#include
#include
#include
#include
#include
#include
using namespace std;
int nCases;
int M, N;
int dp(int m, int n)
{
if(m == 0 || n == 1)
return 1;
if(m < n) //这个地方是m < n ,而不是 m <= n,先开始画蛇添足加了“=”,结果没输出结果。
//才发现,如果加了“=”,则适中递归退不出来。
return dp(m, m);
else
return dp(m-n, n) + dp(m, n-1);
}
int main()
{
scanf("%d", &nCases;);
while(nCases--)
{
scanf("%d %d", &M;, &N;);
printf("%d\n", dp(M, N));
}
return 0;
}
//也算是一道经典的DP把,刚开始做DP题这道题目倒是不错! //不是很难,可以理解DP的简便。