学步园

题目连接：点击打开链接

刚从队友那学来的。

/*
  Nyoj 90 整数划分.
  题大意:把n划分成不大于m的种类有多少？
  例如:整数6可以划分成(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)
  思路:那么一个数n划分成不大于m的种类有多少种情况呢?
  当n>m时,可以分成包含m和不包含m的.
  当n==m时就是,把n分成不大于m-1的情况在加上一个n这种情况.
  当n<m时就相当于把n分成不大于n的这种情况.
*/
//递归求解.
#include<stdio.h>
int fun(int n,int m)
{
    if(n==1||m==1) return 1;
    if(n<=m) return fun(n,n-1)+1;
    if(n>m) return fun(n-m,m)+fun(n,m-1);
//    if(n==m) return fun(n,m-1)+1;
}
int main()
{
    int M;
    scanf("%d",&M);
    while(M--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",fun(n,n));
    }
    return 0;
}
//递推法
#include<stdio.h>
#include<string.h>
const int N=12;
int Map[N][N];
void BuildMap()
{
    memset(Map,0,sizeof(Map));
    Map[1][1]=1;
    for(int i=0;i<=10;i++)
    for(int j=1;j<=10;j++)
    if(i<=j) Map[i][j]=Map[i][i-1]+1;
    else Map[i][j]=Map[i-j][j]+Map[i][j-1];
}
int main()
{
    BuildMap();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",Map[n][n]);
    }
    return 0;
}
//由于该题的数据只有10组，可以直接打表就可以.
#include<stdio.h>
const int f[12]={0,1,2,3,5,7,11,15,22,30,42};
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",f[n]);
    }
}

不断的总结是不错的。