智商的确是太拙计了,以前看过整数划分问题,现在还是不会做,
设函数F(n,m)为整数n的划分中最大的整数是m,
1.如果n等于1或者m等于1,肯定只有一种划分,即全是1的划分
2.如果n等于m,肯定会出现一种划分,即一个数n,然后剩下的划分就是 F(n,m-1);
3.如果n<m,划分中不可能出现负数,所以划分数等于F(n,n)
4.对于剩下的一般情况,第一种情况,n被划分为 m+m1+m2+m3....... ,其中m是最大的,那么剩下的数为n-m,其中m1,m2,m3.....中也可能出现m,即F(n-m,m);
第二种情况,n被划分为 m1+m2+m3....... ,其中所有的数均小于m,即 F(n,m-1);
对于这道题n算是比较大的,所以加上记忆化
code:
#include <iostream> #define LL __int64 using namespace std; LL dat[121][121]; LL Deliver(int n,int max) { if(dat[n][max]) return dat[n][max]; if(n==1 || max==1) return dat[n][max] = 1; if(n==max) return dat[n][max] = Deliver(n,max-1)+1; if(n<max) return dat[n][max] = Deliver(n,n); return dat[n][max] = Deliver(n-max,max)+Deliver(n,max-1); } int main() { int n; while(cin>>n) { cout<< Deliver(n,n) <<endl; } return 0; }