算法提高 數的劃分

算法提高 數的劃分

時間限制：1.0s 記憶體限制：256.0MB

送出此題

問題描述

　　一個正整數可以劃分為多個正整數的和，比如n=3時：

　　3；1＋2；1＋1＋1；

　　共有三種劃分方法。

　　給出一個正整數，問有多少種劃分方法。

輸入格式

　　一個正整數n

輸出格式

　　一個正整數，表示劃分方案數

樣例輸入

3

樣例輸出

3

資料規模和約定

　　n<=100

之前有一題，數的劃分

與此題類似，不過是此題所得的數，可以為0而已。

此題可以看作，是将n分成了n份，并且每份可以是0.

例如 n=3時，分成

3，0，0

1，2，0

1，1，1

#include<iostream>
using namespace std;
int maxsum[][];//maxsum[i][j]表示将i分成j份；
int main()
{
    int n;
    cin>>n;
    for (int i=;i<=n;i++)
    {
        maxsum[i][]=;//将i分成1份，有一種
    }
    for (int i=;i<=n;i++)
    {
        maxsum[][i]=;//将一分成i份 ，有一種
    }
    for (int i=;i<=n;i++)
    {
        for (int j=;j<=n;j++)
        {
            if (i<j)當i<j時，因為此時最多分成i份，實際上相當于将i分成i份
                maxsum[i][j]=maxsum[i][i];
            else if(i==j) //當i==j時，分兩種情況，一種是每份分1，
                //隻有一種分法，第二種至少有一份為0，此時相當于a[i][j-1]
                maxsum[i][j]=maxsum[i][j-]+;
            else if (i>j)//當m>n時，也分兩種情況，一種是至少有一份為0，
                //相當于a[i][j-1],第二種，先将j分出來，然後将i-j再分成j份，此時相當于a
                maxsum[i][j]=maxsum[i-j][j]+maxsum[i][j-];
        }
    }
   cout<<maxsum[n][n];

    return ;
}