算法1

(分治)

状态表示：
f[n][m]表示n的m划分

LL solve(int n , int m ){  //n的m划分,将n分成m组数的和
    //如果n <= 1    显然只能分成一组 
    //如果m == 1    显然只能分成一组
    if( n == 1 || m == 1)    return 1 ;

    //如果n > m 
    //包含m：solve(n-m,m)
    //不包含m: solve(n-m , m-1 );
    if( n > m ) return (solve(n-m,m)+solve(n,m-1))%mod;

    //如果n < m , solve(n,m) == solve(n,n)
    if(n < m )  return solve(n,n)%mod ; 

    //如果包含n==m,总数 = 包含n + 不包含n的划分,即n的m-1划分
    if(n == m ) return  (1+solve(n,m-1))%mod ;

}

C++ 代码

#include <iostream>

using namespace std;

const int mod = 1e9+7;

const int N = 1010;

int f[N][N] ;
int main()
{
    int n ; 
    cin >> n ; 

    for(int i = 1 ; i <= n ; i++)
        f[1][i] = f[i][1] = 1;     

    for(int i = 2 ; i <= n ; i++ ){
        for(int j = 2; j <= n ; j++ ){
            if(i == j)  f[i][j] = (1+f[i][j-1])%mod ;
            else if(i > j)   f[i][j] = (f[i-j][j]+f[i][j-1])%mod ;
            else    f[i][j] = f[i][i]%mod; 
        }
    }

    cout << f[n][n] << endl;

    return 0;
}

算法2

(完全背包法) $O(n^2)$

状态表示：
$f[i][j]$表示从$0~i$中选，背包恰重$j$的方案数

f[i][j] = f[i-1][j] + f[i][j-i] + f[i][j-2i] + … + f[i][j-si] ;

f[i][j-i] = f[i-1][j-i] + f[i][j-2i] + … + f[i][j-si] ;

状态转移方程：
$f[i][j] = f[i-1][j] + f[i][j-i];$

C++ 代码

#include <iostream>

using namespace std;


typedef long long LL ;

const int mod = 1e9+7;

const int N = 1010;

int f[N][N] ;
//从前面的i个物品当中选质量恰为j的重量的方法数

int main()
{
    int n ; 
    cin >> n ; 

    //二维
    for(int i = 0 ; i <= n ; i++)
        f[i][0] = 1;

    for(int i = 1 ; i <= n ; i++ ){
        for(int j = 0 ; j <= n ; j++ ){ //j >= i
            if(j >= i )
                f[i][j] = (f[i-1][j] + f[i][j-i])%mod;
            else    
                f[i][j] = f[i-1][j] ;
        }
    }

    //一维
    /*
    f[0] = 1;

    for(int i = 1 ; i <= n ; i++ )
        for(int j = 0 ; j <= n ; j++ )
            f[j] = (f[j] + f[j-i])%mod;

    cout << f[n] << endl;
    */
    cout << f[n][n] << endl;

    return 0;
}

算法3

(其他状态表示的方法) $O(n^2)$

状态表示：
$f[i][j]$表示总和为i，总个数为j的方案数

状态转移方程：
$f[i][j] = f[i - 1][j - 1] + f[i - j][j];$

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N][N];

int main()
{
    cin >> n;

    f[1][1] = 1;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

    //注意求和
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;

    cout << res << endl;

    return 0;
}