一本通递归经典 1206：放苹果

1206：放苹果

一.题目大意

        如题意，注意苹果和盘子都不区分，并且可以由空的盘子，区别于一本通递归经典 1315：【例4.5】集合的划分

二.选择算法

显然是递归，从大状态分解出很多小状态来求解

0.递归的参数 n表示苹果数,m表示盘子数

1.单层分解子问题的逻辑

        1.如果可以没有空盘子（n>=m）分类两种情况  ：   最后一个盘子都不空（由于不区分盘子，所以最后一个不空就表示都不空），剩下的交给递归；最后一个盘子放空，剩下的交给递归

        2.肯定有空盘子（else）空盘子不考虑，其余交给递归

        3.注：在思考递归或者DFS这类题（DP、BFS）等不重不漏的搜索都一样，都不要管小规模问题到第怎么结局，只需要考虑边界和单层的逻辑，否则分解子问题就会出现逻辑上的问题（逻辑不自洽，简称决策错误QWQ）

2.递归边界

        苹果或者盘子没有或者唯一的时候，答案都是1(m<=1 && n<=1)return 1

三.代码实现

#include
using namespace std;int t,n,m;int dfs(int x,int y){if(x==1 || x==0)return 1;if(y==1 || y==0)return 1;if(x>=y){return dfs(x-y,y)+dfs(x,y-1);}else return dfs(x,x);
}int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);printf("%d\n",dfs(n,m)); }
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！