题目描述

求正整数 n 的分割数，最大部分为 m，即 n 可以分割为不大于 m 的正整数的和，并且按递增顺序排列。例如，使用 4 作为最大数对 6 进行分割的方式有 9 种。

1.  6 = 2 + 4
2.  6 = 1 + 1 + 4
3.  6 = 3 + 3
4.  6 = 1 + 2 + 3
5.  6 = 1 + 1 + 1 + 3
6.  6 = 2 + 2 + 2
7.  6 = 1 + 1 + 2 + 2
8.  6 = 1 + 1 + 1 + 1 + 2
9.  6 = 1 + 1 + 1 + 1 + 1 + 1

样例输入

24 9

样例输出

1076

解题分析

其实本题带有明显的递归性质，关键在于如何确定递归的边界条件和递归的逻辑。其实从例子中我们可以简单地做一个分类，在n=6,m=4的条件下，分割数中可以划分为两类，一类是出现了数字m的，这个时候我们只需要对n-m再分割即可，另一类是没有出现数字m的，我们可以把这个问题划为n=6,m=3（也就是n,m-1）。

考虑一下边界条件，如果m<=0，不存在，0种分割方式；如果n=0，则只有一种分割方式1=1（因为n=0说明上一层递归中n=m，若有m则只有一种分割方法）；如果n<0，不存在，为0种分割方式。

代码实现

#include <iostream>
using namespace std;

int f(int n,int m){
	if(m<=0) return 0;
	if(n==0) return 1;
	if(n<=0) return 0;
	return f(n-m,m)+f(n,m-1);
}


int main(){
	int n,m;
	cin>>n>>m;
	cout<<f(n,m)<<endl;
	return 0;
}