整数划分问题(分治递归)-爱代码爱编程

用最大为m凑出n的数量

图解：

代码如下：

#include <bits/stdc++.h>
using namespace std;

int f(int n,int m)
{
    if(n==1||m==1) return 1;          //递归出口,f(1,m)=1,f(n,1)=1,1个1或者n个1 
    else if(m>n) return f(n,n);         //f(n,m)=f(n,n) 
    else if(n==m) return f(n,n-1)+1; //f(n,n)=1+f(n,n-1) 
    else return f(n,m-1)+f(n-m,m);   //f(n,m)=f(n,m-1)+f(n-m,m) 
}

int main() {
    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",f(n,n)); //n的m划分的个数f(n,m) 
    } 
    return 0;
}