简单的整数划分 #

题目描述：#

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

Input：#

标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。

Output：#

对于每组测试数据，输出N的划分数

Input	Output
`5`	`7`

Hint：#

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

1
#include<iostream>
2
#include<algorithm>
3
using namespace std;
4
int main(){
5
  int  v[55][55]={0},a[55];
6
  int N=51,n;v[0][0]=1;
7
  for(int i = 1; i <= N; i++) //硬币种类
8
  for(int j = 1; j <= N; j++)//硬币个数
9
    for(int k=i;k<=N;k++){//背包容量
10
      v[j][k]+=v[j-1][k-i];
11
            //第一种硬币有一个v[j][k]，第二种硬币有一个v[j][k]所以要自增;
12
/*根据Coin Change那一题想的思路,题目相当于有5种硬币(1,2,3,4,5)每种硬币最多用5个(5个面值为1的),背包容量为5*/
13
/*v[j][k]表示用j个硬币装满k容量的口袋也相当于在相同空间时，i-1种硬币装法加上j-1个硬币k-a[i]空间的装法*/
14
    }
15
  while(cin>>n){
16
    int sum=0;
17
    for(int i=0;i<=N;i++){
18
    sum+=v[i][n];
19
    }
20
    cout<<sum<<endl;
21
  }
22
}