整数区划

整数划分

正整数 n 的这种表示称为正整数 n 的划分。求正整数 n 的不同划分个数。 

例如正整数6有如下11种不同的划分：

    6；

    5+1；

    4+2，4+1+1；

    3+3，3+2+1，3+1+1+1；

    2+2+2，2+2+1+1，2+1+1+1+1；

    1+1+1+1+1+1。

如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n₁不大于m的划分个数记作q(n, m)。可以建立q(n, m)的如下递归关系.

(3) q(n, n)=1+q(n, n-1);

正整数n的划分由n₁=n的划分和n₁≤n-1的)划分组成。

(4) q(n, m)=q(n, m-1)+q(n-m, m), n>m>1;

正整数n的最大加数n₁不大于m的划分由n₁=m的划分和

n₁≤m-1 的划分组成。

如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n₁不大于m的划分个数记作q(n, m)。可以建立q(n, m)的如下递归关系。

//
//  main.cpp
//  整数划分
//
//  Created by Fangpin on 15/3/23.
//  Copyright (c) 2015年 FangPin. All rights reserved.
//
#include <cstring>
#include <iostream>
using namespace std;
int dp[50][50];
int f(int n,int m){
    if(dp[n][m]) return dp[n][m];
    if(n==1 && m==1) return dp[1][1]=1;
    if(m>n) return dp[n][m]=dp[n][n]=f(n,n);
    else if(n==m) return dp[n][n]=1+f(n,m-1);
    else return dp[n][m]=f(n,m-1)+f(n-m,m);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int n;
    memset(dp,0,sizeof(dp));
    dp[1][1]=1;
    for(int i=1;i<50;++i){
        dp[i][1]=1;
    }
    while(cin>>n){
        cout<<f(n,n)<<endl;
    }
    return 0;
}